상영 전 좌석 기록 복원

문제

영화관의 한 상영관에서 좌석 예약 화면을 다시 구성하려 한다. 이 상영관에는 1번부터 N번까지 번호가 붙은 좌석이 있으며, 기록이 시작되기 직전에는 모든 좌석이 비어 있다. 기록에는 예약 요청과 취소 요청이 도착한 순서대로 남아 있다. 요청이 실패한 경우도 기록에서 삭제되지 않으므로, 각 요청을 실제 상태에 맞게 처리해야 한다. 예약 요청은 B x로 나타내며 x번 좌석을 예약하려는 요청이다. 요청을 처리하는 순간 x번 좌석이 비어 있다면 요청이 성공하고 그 좌석은 예약된 상태가 된다. 이미 예약된 좌석이라면 요청은 실패하며 좌석 상태는 바뀌지 않는다. 다른 빈 좌석을 대신 배정하는 일은 없다. 같은 좌석을 향한 예약 요청이 여러 번 등장하더라도 각각 별도의 요청으로 처리한다. 취소 요청은 C x로 나타내며 x번 좌석의 예약을 취소하려는 요청이다. 요청을 처리하는 순간 x번 좌석이 예약되어 있다면 요청이 성공하고 그 좌석은 빈 상태가 된다. 이미 비어 있는 좌석이라면 요청은 실패하며 상태는 그대로 유지된다. 이 문제에서는 예약자 정보는 관리하지 않으며, 예약되어 있는 좌석에 대한 취소 요청은 항상 성공한다. 모든 요청은 입력된 순서대로 한 번씩 처리한다. 취소로 비게 된 좌석은 이후의 예약 요청으로 다시 예약할 수 있다. 앞에서 실패한 요청을 뒤의 상태 변화에 맞추어 재시도하지는 않는다. 또한 예약 요청과 취소 요청을 한꺼번에 상쇄해서 처리해서는 안 된다. 같은 요청들이 등장하더라도 도착 순서에 따라 실패 횟수가 달라질 수 있기 때문이다. 마지막 요청까지 처리한 시점에 예약되어 있는 좌석 수와 전체 실패 요청 수를 구한다. 이어서 최종적으로 예약된 좌석 번호를 작은 번호부터 출력한다. 실패 요청 수에는 실패한 예약과 실패한 취소를 모두 포함한다. 최종 예약 좌석이 하나도 없다면 좌석 목록 대신 0 하나를 출력한다. 중간에 예약된 적이 있더라도 마지막에 비어 있는 좌석은 목록에 포함하지 않는다.

입력

첫째 줄에 좌석 수 N과 요청 수 M이 공백으로 주어진다. N과 M은 정수이며 1≤N≤100,000, 1≤M≤30,000이다.
다음 M개 줄에 요청 종류와 좌석 번호 x가 공백으로 주어진다. 요청 종류는 B 또는 C이며, x는 1≤x≤N을 만족하는 정수다.

출력

첫째 줄에 최종 예약 좌석 수와 전체 실패 요청 수를 공백으로 구분하여 출력한다. 둘째 줄에 최종 예약된 좌석 번호를 오름차순으로 공백으로 구분하여 출력한다. 최종 예약 좌석이 없으면 둘째 줄에 0을 출력한다.

5 7
B 3
B 3
C 2
B 1
C 3
B 5
B 3

3 2
1 3 5

1 4
C 1
B 1
C 1
C 1

0 2
0

4 3
B 4
B 2
B 1

3 0
1 2 4

출처: Devin.KR 자체 제작