가장 앞 번호의 주차 칸

문제

한 주차장에는 1번부터 K번까지 번호가 붙은 주차 칸이 있다. 각 칸에는 자동차 한 대만 주차할 수 있으며, 처음에는 모든 칸이 비어 있다. 관리인은 입구에서 도착한 자동차에 칸을 배정하고, 출구에서 전달받은 번호를 바탕으로 해당 칸을 비운다. 관리 기록에는 자동차의 이름 대신 도착 작업과 칸을 비우는 작업만 순서대로 적혀 있다. A 작업은 자동차 한 대가 도착했다는 뜻이다. 이때 비어 있는 칸 가운데 번호가 가장 작은 칸에 자동차를 주차시키고, 배정한 칸 번호를 안내한다. 빈 칸이 여러 개라도 다른 기준은 사용하지 않는다. 비어 있는 칸이 하나도 없다면 자동차는 주차하지 않고 바로 떠나며, 안내 번호는 0이다. 떠난 자동차는 이후에 빈 칸이 생겨도 자동으로 돌아오지 않는다. L x 작업은 x번 칸을 비우라는 뜻이다. x번 칸에 자동차가 있다면 그 자동차가 출차하여 칸이 빈 상태가 된다. 이미 비어 있는 칸의 번호가 전달될 수도 있으며, 이 경우에는 상태를 바꾸지 않는다. 같은 번호를 연속해서 비우라는 작업이 들어와도 빈 칸이 여러 개 생기는 것은 아니다. L 작업에서는 안내 번호를 출력하지 않는다. 각 작업은 앞선 작업의 처리가 완전히 끝난 뒤 실행한다. 따라서 어떤 칸을 비운 직후 자동차가 도착하면 그 칸도 배정 후보가 된다. 한 번 배정했던 칸이라도 출차한 뒤에는 다시 사용할 수 있다. 주어진 모든 작업을 순서대로 처리하면서 각 A 작업의 안내 번호를 구하는 프로그램을 작성한다. 입력에는 A 작업이 적어도 하나 포함되며, 안내 번호는 자동차가 도착한 순서대로 출력해야 한다.

입력

첫째 줄에 주차 칸 수 K와 작업 수 M이 공백으로 구분되어 주어진다. K는 1 이상 100,000 이하, M은 1 이상 20,000 이하의 정수다.
다음 M개 줄에는 A 또는 L x 형식의 작업이 하나씩 주어진다. x는 1 이상 K 이하의 정수다. A 작업이 적어도 하나 주어진다.

출력

각 A 작업에서 배정한 칸 번호를 한 줄에 하나씩 출력한다. 해당 작업에서 빈 칸이 없다면 0을 출력한다.

3 9
A
A
L 1
A
A
A
L 2
L 2
A

1
2
1
3
0
2

1 5
L 1
A
A
L 1
A

1
0
1

출처: Devin.KR 자체 제작