시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 71 24 19 31.148%

문제

노는 걸 좋아하는 필기는 알고 보니 재벌 2세였다. 그래서 새로운 형태의 파티룸 사업을 시작하려 한다. 이 사업은 손님들에게 원하는 넓이의 방을 원하는 시간만큼 제공하는 것을 목표로 하고 있다. 어느 한 폐교를 사들인 필기는 직육면체 형태로 건물을 개조하였다. 그리고 가벼운 임시 벽을 세워 N개의 1평짜리 방들이 연속적으로 늘어선 형태로 개조하였다. 각 방에는 1부터 N까지 가장 왼쪽부터 순서대로 번호가 붙어있다.

필기는 손님이 올 때마다 인원 수 X와 원하는 평수 Y를 물어본다. 그러면 연속적으로 비어있는 Y개의 방을 찾아 벽들을 제거하고 하나의 Y평짜리 방으로 만들어 손님에게 제공한다. 이때 필기는 관리하기 쉽도록 새로운 파티룸을 되도록 왼쪽에 가깝게 만들고 싶다. (가능한 방 번호가 가장 낮은 곳에 할당하고 싶다)

사용 중인 방에는 추가 손님이 입장할 수 있고 일부가 퇴실할 수도 있다. 한 방의 손님이 모두 퇴실하면 필기는 그 방을 청소하고 치웠던 벽을 다시 설치한다. 그 방은 원래의 연속적인 1평짜리 방으로 나누어져 새로운 손님이 할당받을 수 있다.

할당된 방은 가장 왼쪽 방의 번호 L과 가장 오른쪽 방의 번호 R로 표현할 수 있다. "L R"을 출력하라 하면 할당된 방의 가장 왼쪽, 가장 오른쪽 방 번호를 출력하면 된다.

필기는 다음과 같은 3가지 업무를 처리해야 한다. 업무에 있는 모든 수는 정수이다.

  • new X Y (1 ≤ X ≤ 2,147,483,647, 1 ≤ Y ≤ N): X명의 손님이 Y평의 파티룸을 원한다. Y평의 새로운 파티룸을 만들 수 있다면 새 방을 할당하고 "L R"을 출력한다. 만약 불가능하다면 "REJECTED"를 출력하고 손님을 거부한다.
  • in A B (1 ≤ B): 시간순으로 A번째 순서로 할당된 파티룸에 B명의 손님이 추가로 더 들어온다. 이미 치워진 방도 포함해서 A번째로 할당된 방을 찾아야 한다. 이 방은 지금 할당되어 있는 방이며, 추가로 들어온 이후 방에 있는 사람이 2,147,483,647명을 넘지 않음이 보장된다. 이 작업에 대해서 출력은 하지 않는다.
  • out A B (1 ≤ B): A번째 순서로 할당된 파티룸에 B명의 손님이 퇴실한다. 파티룸에 있는 손님보다 더 많은 손님이 퇴실하는 경우는 없음이 보장된다. 만약 파티룸에서 손님이 모두 퇴실한다면 "CLEAN L R"를 출력한다.

사업을 해본 적이 없는 필기는 여러분에게 도움을 청했다. 필기를 도와 건물을 관리하는 프로그램을 작성해 보자.

입력

첫 줄에 N과 Q가 주어진다. (1 ≤ N, Q ≤ 5000)

이어지는 Q개의 줄마다 세 개의 업무 중 하나의 업무가 주어진다.

출력

각 쿼리에 대해 알맞은 답을 출력한다.

예제 입력 1

4 6
new 4 1
new 4 2
in 1 1
out 2 4
new 4 3
out 1 5

예제 출력 1

1 1
2 3
CLEAN 2 3
2 4
CLEAN 1 1

예제 입력 2

4 4
new 4 1
new 4 4
new 3 3
out 2 3

예제 출력 2

1 1
REJECTED
2 4
CLEAN 2 4

예제 입력 3

6 6
new 4 1
new 4 2
in 1 1
new 4 3
out 2 4
new 4 2

예제 출력 3

1 1
2 3
4 6
CLEAN 2 3
2 3

노트

출처

  • 문제의 잘못된 점을 전체적으로 찾은 사람: jh05013
  • 문제를 만든 사람: zlqhemqhdkm