도서관 표지 보수대

문제

도서관에는 책의 낡은 표지를 보수하는 작업대가 하나 있다. 책마다 작업대에 도착하는 시각과 보수에 필요한 시간이 다르다. 담당자는 모든 책의 도착 기록을 받은 뒤, 정해진 접수 규칙에 따라 책을 처리한다. 기록은 도착 시각 순서로 주어지지 않을 수 있으므로 입력된 순서와 실제 작업 순서를 구별해야 한다. 각 책에는 입력 순서대로 1번부터 N번까지 번호가 붙는다. 작업대는 시각 0부터 사용할 수 있으며, 한 번에 책 한 권만 보수할 수 있다. 도착 시각이 빠른 책부터 보수하고, 도착 시각이 같은 책끼리는 번호가 작은 책부터 보수한다. 이미 시작한 보수 작업은 다른 책이 도착하더라도 중단하지 않는다. 아직 도착하지 않은 책을 미리 보수할 수는 없다. 작업대가 비었을 때 처리 순서상 다음 책이 이미 도착했다면 즉시 보수를 시작한다. 다음 책이 아직 도착하지 않았다면 그 책의 도착 시각까지 기다린 뒤 시작한다. 책 한 권의 보수가 끝나면 별도의 정리 시간 없이 다음 책을 처리할 수 있다. 따라서 어떤 책의 보수가 끝나는 시각과 다른 책의 보수가 시작하는 시각이 같아도 된다. 도착 시각과 보수 시간은 모두 정수 단위로 주어진다. 도서관 안내 화면에는 각 책의 보수 완료 시각을 책 번호 순서대로 표시해야 한다. 실제 보수 순서대로 출력하면 안 된다. 모든 책은 반드시 보수를 마칠 수 있으며, 마감 시각이나 작업 중단은 없다. 책이 한 권도 접수되지 않은 경우에는 안내 화면에 표시할 완료 기록이 없다는 뜻으로 EMPTY를 출력한다. 주어진 기록으로 안내 화면에 표시할 내용을 구하는 프로그램을 작성한다.

입력

첫째 줄에 책의 수 N이 주어진다. 다음 N개 줄의 i번째 줄에 i번 책의 도착 시각 A_i와 보수 시간 T_i가 주어진다.
모든 입력값은 정수이다. 0≤N≤10,000, 0≤A_i≤1,000,000, 1≤T_i≤1,000이다.

출력

N이 양수이면 1번 책부터 N번 책까지 각 책의 보수 완료 시각을 한 줄에 하나씩 출력한다. N이 0이면 EMPTY를 한 줄에 출력한다.

4
5 3
0 4
5 2
1 3

10
4
12
7

3
2 2
2 1
10 2

4
5
12

0

EMPTY

출처: Devin.KR 자체 제작