예약 순서 조정 기록

문제

한 병원은 진료를 시작하기 전에 당일 예약자들의 호출 순서를 확정한다. 예약자는 1번부터 N번까지의 서로 다른 예약 번호를 받았으며, 처음 호출 순서는 1번, 2번, …, N번이다. 접수 담당자는 준비 상황과 예약 취소를 반영하기 위해 순서 조정 명령을 차례대로 남겼다. 모든 명령을 처리한 뒤 남아 있는 예약자의 호출 순서를 알아내야 한다. 명령 M a b는 예약자 a를 현재 위치에서 빼낸 다음 예약자 b의 바로 뒤에 넣는다는 뜻이다. 이 명령에서는 a와 b가 서로 다르고 두 예약자가 모두 현재 호출 순서에 남아 있다. a가 이미 b의 바로 뒤에 있으면 순서는 바뀌지 않는다. a를 옮길 때 a와 b를 제외한 다른 예약자들의 상대적인 순서는 유지된다. 특히 a가 b보다 앞에 있더라도 먼저 a를 빼내고, 남아 있는 b의 위치를 기준으로 삽입한다. 명령 C a는 예약자 a의 예약을 취소하여 현재 호출 순서에서 제거한다는 뜻이다. 취소되는 예약자는 그 명령 직전까지 호출 순서에 남아 있다. 한 번 취소된 예약자는 다시 추가되지 않으며, 이후 명령의 대상으로도 등장하지 않는다. 명령에 사용되는 번호는 현재 몇 번째인지를 나타내는 위치가 아니라 처음 부여받은 예약 번호이다. 호출 순서의 맨 앞이나 맨 뒤에 있는 예약자도 다른 예약자와 같은 규칙으로 옮기거나 취소할 수 있다. 모든 예약이 취소되는 경우도 있다. 명령은 입력에 주어진 순서대로 정확히 한 번씩 적용한다. 마지막 명령까지 적용한 후 남은 예약 번호를 호출 순서대로 출력하는 프로그램을 작성한다. 명령이 하나도 없으면 처음 순서를 그대로 출력하며, 남은 예약자가 없으면 예약 번호 대신 0 하나를 출력한다.

입력

첫 줄에 정수 N과 Q가 주어진다. N은 1 이상 20,000 이하이고 Q는 0 이상 20,000 이하이다.
다음 Q개 줄에 M a b 또는 C a 형식의 명령이 주어진다. 예약 번호 a와 b는 1 이상 N 이하의 정수이다.
M 명령의 a와 b는 서로 다르며 모두 취소되지 않은 예약자이다. C 명령의 a도 취소되지 않은 예약자이다. 모든 명령이 이 조건을 만족하는 입력만 주어진다.

출력

모든 명령 처리 후 남은 예약 번호를 호출 순서대로 공백으로 구분해 한 줄에 출력한다. 남은 예약자가 없으면 0을 출력한다.

5 4
M 2 4
C 3
M 1 2
M 5 4

4 5 2 1

2 2
C 1
C 2

0

3 0

1 2 3

출처: Devin.KR 자체 제작