배달 앱의 예상 시간 수정

문제

한 배달 앱은 접수된 주문마다 배달까지 남은 예상 시간을 정수 분 단위로 표시한다. 운영자는 주문 접수, 개별 시간 수정, 주문 취소, 전체 지연을 사건 목록에 기록한다. 처음에는 등록된 주문이 없으며, 사건을 입력된 순서대로 모두 처리한 뒤 최종 주문 목록을 만들어야 한다. NEW id t는 번호가 id인 주문을 새로 등록하고 예상 시간을 t분으로 정하는 사건이다. 이때 같은 번호의 주문이 현재 등록되어 있지 않음이 보장된다. 과거에 취소한 주문 번호를 다시 사용하는 것은 가능하며, 다시 등록한 주문은 새로 주어진 예상 시간을 갖는다. SET id t는 현재 등록된 해당 주문의 예상 시간을 t분으로 교체하는 사건이다. 이전 예상 시간에 t를 더하는 것이 아니다. CANCEL id는 현재 등록된 해당 주문을 목록에서 없애는 사건이다. SET과 CANCEL의 대상 주문은 사건 처리 직전에 반드시 등록되어 있다. DELAY d는 그 순간 등록된 모든 주문의 예상 시간을 각각 d분 늘리는 사건이다. 이 사건 이후에 새로 등록되는 주문에는 앞서 발생한 전체 지연을 추가하지 않는다. 등록된 주문이 없을 때 발생한 전체 지연도 이후 주문에 영향을 주지 않는다. 이 목록은 운영자가 예상 수치를 수정한 기록이다. 사건을 하나 처리한다고 실제 시간이 흐르지는 않으므로, 예상 시간을 자동으로 줄이거나 0분인 주문을 자동으로 제거하지 않는다. 모든 사건을 처리한 뒤에는 예상 시간이 작은 주문부터 출력한다. 예상 시간이 같으면 주문 번호가 작은 주문을 먼저 출력한다. 최종적으로 등록된 주문이 없으면 주문 수 0만 출력한다.

입력

첫째 줄에 사건 수를 나타내는 정수 Q가 주어진다. 1 ≤ Q ≤ 20,000이다.
다음 Q개 줄에는 NEW id t, SET id t, CANCEL id, DELAY d 중 하나가 주어진다. 각 항목은 공백으로 구분된다.
주문 번호 id는 1 이상 10,000 이하의 정수다. t는 0 이상 100,000 이하의 정수이고, d는 0 이상 1,000 이하의 정수다. NEW의 번호는 현재 등록되어 있지 않으며, SET과 CANCEL의 번호는 현재 등록되어 있음이 보장된다.

출력

첫째 줄에 최종적으로 등록된 주문 수 K를 출력한다. 이어서 K개 줄에 주문 번호와 최종 예상 시간을 정수로 공백 하나로 구분하여 출력한다. 예상 시간이 작은 순서로 출력하고, 같으면 주문 번호가 작은 순서로 출력한다. K가 0이면 첫째 줄만 출력한다.

8
NEW 8 12
NEW 3 9
DELAY 4
SET 8 7
NEW 5 7
DELAY 2
CANCEL 3
NEW 2 9

3
2 9
5 9
8 9

5
DELAY 100
NEW 4 0
DELAY 3
CANCEL 4
DELAY 8

0

7
NEW 6 20
DELAY 10
SET 6 2
NEW 1 0
CANCEL 6
NEW 6 4
DELAY 1

2
1 1
6 5

출처: Devin.KR 자체 제작