원형 주차 구역의 안내 기록

문제

작은 주차장의 주차 칸은 원형 통로를 따라 배치되어 있다. 칸에는 1번부터 S번까지 번호가 붙어 있으며, S번 다음에는 다시 1번이 이어진다. 차량은 번호로 구분한다. 처음에는 모든 칸이 비어 있고, 어떤 차량도 주차되어 있지 않다. 안내 장치는 입차 요청과 출차 요청을 기록된 순서대로 하나씩 처리한다. 입차 요청에는 차량 번호와 탐색을 시작할 칸 번호가 들어 있다. 해당 차량이 이미 이 주차장에 주차되어 있다면 요청을 거절하고 기존 주차 상태를 그대로 유지한다. 그렇지 않으면 시작 칸부터 번호가 증가하는 방향으로 칸을 살펴본다. 마지막 번호 다음에는 1번으로 돌아가며, 각 칸은 최대 한 번만 살펴본다. 처음 발견한 빈칸에 차량을 주차하고 탐색을 끝낸다. 모든 칸이 차 있다면 입차 요청을 거절한다. 출차 요청에는 차량 번호만 들어 있다. 해당 차량이 주차되어 있으면 그 차량이 차지하던 칸을 비우고 출차를 완료한다. 주차되어 있지 않은 차량에 대한 출차 요청은 아무 상태도 바꾸지 않는다. 한 번 출차한 차량은 이후의 입차 요청으로 다시 주차할 수 있다. 요청을 거절하거나 무시하더라도 다음 요청은 정상적으로 처리한다. 장치는 요청마다 처리 결과 하나를 남긴다. 입차에 성공하면 배정한 칸 번호를, 출차에 성공하면 비워진 칸 번호를 기록한다. 입차가 거절되었거나 출차할 차량이 없으면 0을 기록한다. 따라서 같은 숫자가 기록되더라도 요청 종류에 따라 의미가 다를 수 있다. 모든 요청을 순서대로 처리했을 때 장치가 남기는 결과를 구하는 프로그램을 작성하라. 빈칸 후보가 여러 개일 때는 반드시 정해진 탐색 순서에서 가장 먼저 만나는 칸을 사용해야 한다.

입력

첫째 줄에 주차 칸 수 S와 요청 수 Q가 공백으로 구분되어 주어진다. S와 Q는 정수이며 1≤S≤100, 1≤Q≤10,000이다.
다음 Q개 줄에 요청이 하나씩 주어진다. 입차 요청은 A v p 형식이며, 출차 요청은 D v 형식이다. v는 1 이상 9,999 이하의 정수인 차량 번호이고, p는 1 이상 S 이하의 정수인 탐색 시작 칸이다. 같은 차량에 대한 요청이 여러 번 주어질 수 있으며, 이미 주차된 차량의 입차나 주차되지 않은 차량의 출차도 입력될 수 있다.

출력

각 요청의 처리 결과를 입력 순서대로 한 줄에 하나씩 출력한다. 입차 성공이면 배정한 칸 번호, 출차 성공이면 비워진 칸 번호를 출력한다. 그 외에는 0을 출력한다.

3 7
A 11 3
A 22 3
A 33 1
A 44 2
D 22
A 44 3
D 99

3
1
2
0
1
1
0

1 6
D 7
A 7 1
A 7 1
D 7
A 8 1
D 7

0
1
0
1
1
0

출처: Devin.KR 자체 제작