출발 순서를 미루는 버스

문제

여러 버스 노선이 함께 사용하는 차고지에는 출발을 기다리는 버스의 순서를 관리하는 시스템이 있다. 시스템은 대기 중인 버스들을 맨 앞부터 맨 뒤까지 한 줄로 기록한다. 실제 주차 위치와 관계없이 이 기록에서 맨 앞에 있는 버스가 다음 출발 대상이 된다. 처음에는 대기 중인 버스가 없다. 운영 중에는 세 종류의 지시가 순서대로 들어온다. A x는 식별 번호가 x인 버스를 대기 줄의 맨 뒤에 추가하는 지시다. 각 A 지시의 식별 번호는 전체 입력에서 서로 다르므로, 한 번 출발한 버스가 같은 번호로 다시 추가되는 경우도 없다. 대기 줄에 버스가 하나도 없을 때 추가하면 그 버스가 맨 앞이면서 맨 뒤가 된다. D는 대기 줄의 맨 앞 버스를 출발시키는 지시다. 버스가 있으면 그 버스를 대기 줄에서 제거하고 식별 번호를 출발 기록에 남긴다. 대기 줄이 비어 있으면 출발시킬 버스가 없다는 뜻으로 출발 기록에 0을 남긴다. 빈 대기 줄에 D 지시가 들어와도 이후 지시는 계속 처리한다. R은 맨 앞 버스의 출발을 한 차례 미루는 지시다. 대기 중인 버스가 있으면 맨 앞 버스를 꺼내 대기 줄의 맨 뒤로 옮긴다. 이때 다른 버스들의 상대적인 순서는 그대로 유지한다. 버스가 하나뿐이면 대기 순서는 바뀌지 않으며, 대기 줄이 비어 있으면 아무 일도 하지 않는다. R 지시는 출발 기록을 만들지 않는다. 시스템 점검을 위해 모든 지시를 처리했을 때의 출발 기록과 최종 대기 순서를 복원하려고 한다. D 지시에서 만들어진 기록은 지시가 등장한 순서대로 출력한다. 마지막 대기 순서는 맨 앞 버스부터 출력한다. 출발 기록이 하나도 없거나 마지막에 기다리는 버스가 없는 경우에도 각 목록의 길이를 명확하게 알 수 있도록 정해진 형식을 지켜야 한다.

입력

첫째 줄에 지시의 개수 M이 주어진다. M은 정수이며 1≤M≤30,000이다.
다음 M개 줄에는 A x, D, R 중 하나의 지시가 주어진다. x는 1≤x≤10^9인 정수이며, 모든 A 지시의 x는 서로 다르다.
D 또는 R 지시가 빈 대기 줄에 주어질 수 있다.

출력

첫째 줄에 출발 기록의 개수 K를 출력한다. 둘째 줄에 K개의 출발 기록을 공백으로 구분하여 출력한다. K가 0이면 빈 줄을 출력한다. 셋째 줄에 마지막 대기 버스의 수 W를 출력한다. 넷째 줄에 W개의 식별 번호를 맨 앞부터 공백으로 구분하여 출력한다. W가 0이면 빈 줄을 출력한다.

8
A 41
A 72
R
D
A 19
R
D
D

3
72 19 41
0

6
D
R
A 8
A 5
R
D

2
0 5
1
8

3
A 17
R
A 23

0

2
17 23

출처: Devin.KR 자체 제작