진료실 시간 블록 배정

문제

한 병원의 진료실은 하루를 2^K개의 시간 칸으로 나누어 쓴다. 칸의 번호는 왼쪽부터 0, 1, ..., 2^K - 1이다. 진료 예약은 연속된 2^j개의 칸을 차지하며, 시작 칸 번호가 2^j의 배수여야 한다. 즉 하루 전체를 반으로 쪼개고 다시 반으로 쪼개는 재귀적 구조에서 하나의 조각에 해당하는 블록만 쓸 수 있다. 요청은 순서대로 처리하며 두 종류가 있다. A j는 크기 2^j의 새 예약 요청이다. 이 크기의 블록 중 아직 어떤 예약과도 겹치지 않는 것이 있다면, 그중 시작 칸 번호가 가장 작은 블록을 배정하고 그 시작 칸 번호를 출력한다. 그런 블록이 없으면 -1을 출력하고 아무것도 배정하지 않는다. A 요청에는 성공 여부와 관계없이 처음 나온 순서대로 1, 2, 3, ... 번호가 매겨진다. C x는 x번 A 요청으로 배정된 예약을 취소하는 요청이다. 그 예약이 실제로 배정되어 있고 아직 취소되지 않았다면 취소하고 OK를 출력하며, 해당 블록은 다시 비어 다른 요청에 쓰일 수 있다. 배정에 실패했거나 이미 취소된 예약이라면 NO를 출력한다. 취소로 이웃한 블록이 함께 비게 되면 더 큰 블록도 다시 사용할 수 있게 된다.

입력

첫 줄에 정수 K와 Q가 공백으로 구분되어 주어진다. 이어서 Q개의 줄에 요청이 하나씩 주어진다. A j 형식에서 0 ≤ j ≤ K이고, C x 형식에서 x는 그 시점까지 나온 A 요청의 수 이하의 양의 정수다. 0 ≤ K ≤ 20, 1 ≤ Q ≤ 200000.

출력

각 요청마다 한 줄씩 결과를 출력한다. A 요청은 시작 칸 번호 또는 -1, C 요청은 OK 또는 NO를 출력한다.

3 8
A 2
A 1
A 2
A 0
C 1
A 1
C 3
C 1

0
4
-1
6
OK
0
NO
NO

0 4
A 0
A 0
C 1
A 0

0
-1
OK
0

출처: Devin.KR 자체 제작