통로를 넘지 않는 항공권

문제

한 항공권 예약 시스템은 같은 일행의 좌석을 한 줄에 붙여 배정한다. 비행기에는 1번부터 R번까지의 좌석 줄이 있고, 각 줄에는 왼쪽부터 1번부터 6번까지 여섯 좌석이 있다. 3번 좌석과 4번 좌석 사이에는 통로가 있으므로, 1·2·3번 좌석은 왼쪽 구역이고 4·5·6번 좌석은 오른쪽 구역이다. 처음에는 모든 좌석이 비어 있다. 시스템에는 예약 요청과 취소 요청이 총 Q개 들어온다. 요청에는 입력 순서대로 1번부터 Q번까지 번호를 붙인다. 예약 요청 B r k p는 r번 줄에서 k명의 좌석을 예약하라는 뜻이다. p가 L이면 왼쪽 구역만, R이면 오른쪽 구역만 살펴본다. p가 A이면 두 구역을 모두 살펴본다. 일행은 같은 구역 안에서 번호가 연속인 k개의 빈 좌석을 받아야 한다. 통로를 사이에 둔 좌석은 번호가 연속이어도 함께 배정할 수 없다. 조건을 만족하는 배정 방법이 여러 개면 시작 좌석 번호가 가장 작은 방법을 선택한다. 선택한 좌석은 즉시 사용 중이 된다. 조건을 만족하는 방법이 없으면 예약은 실패하며 어떤 좌석도 바꾸지 않는다. 요청한 줄 이외의 줄에서 좌석을 찾거나, 일행을 나누어 배정하지 않는다. 취소 요청 C t는 t번 요청으로 생성된 예약을 취소하라는 뜻이다. t번 요청이 성공한 예약 요청이고 아직 취소되지 않았다면, 그 예약에 배정한 좌석을 모두 빈 좌석으로 바꾸고 취소에 성공한다. t번 요청이 실패한 예약 요청이거나, 이미 취소된 예약이거나, 취소 요청이었다면 취소에 실패한다. 취소 요청의 성공 여부와 관계없이 해당 취소 요청 자체가 새로운 예약이 되는 일은 없다. 각 요청의 처리 결과를 입력 순서대로 출력한다. 예약 요청에는 배정한 첫 좌석 번호를 출력하고 실패하면 0을 출력한다. 취소 요청에는 성공하면 1, 실패하면 0을 출력한다. 모든 요청은 앞선 요청의 처리가 완전히 끝난 뒤 처리한다.

입력

첫째 줄에 정수 R, Q가 주어진다. 1 ≤ R ≤ 1,000, 1 ≤ Q ≤ 20,000이다. 다음 Q개 줄에는 요청이 하나씩 주어진다. 예약 요청은 B r k p 형식이며, r과 k는 정수로 1 ≤ r ≤ R, 1 ≤ k ≤ 3이고 p는 L, R, A 중 하나다. i번 취소 요청은 C t 형식이며, t는 1 ≤ t < i인 정수다. 따라서 첫 번째 요청은 반드시 예약 요청이다.

출력

각 예약 요청에 대해 성공하면 배정한 연속 좌석 중 가장 작은 좌석 번호를, 실패하면 0을 출력한다. 각 취소 요청에 대해 성공하면 1, 실패하면 0을 출력한다. 요청마다 한 줄에 하나의 정수를 출력하며, 성공한 요청이 없어도 모든 요청의 결과를 출력한다.

1 9
B 1 2 A
B 1 2 A
B 1 2 A
C 1
B 1 3 L
B 1 1 R
C 1
C 2
B 1 3 A

1
4
0
1
1
6
0
1
0

2 8
B 2 3 R
B 2 1 R
C 2
C 3
C 1
B 2 2 A
B 2 2 L
B 1 3 A

4
0
0
0
1
1
0
1

출처: Devin.KR 자체 제작