카페의 회전 진열대

문제

카페에서는 원형 진열대에 N개의 상품을 올려 두고 판매 전 배치를 조정한다. 진열대를 바라보는 직원의 위치는 고정되어 있다. 직원이 보는 진열 위치에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있으며, N번 다음은 다시 1번이다. 각 상품에는 상품 종류를 나타내는 양의 정수가 적혀 있다. 같은 종류의 상품이 여러 위치에 놓여 있어도 된다. 직원은 두 종류의 작업을 수행한다. 첫 번째는 진열대 전체를 시계 방향으로 k칸 회전하는 작업이다. 한 칸 회전하면 1번 위치의 상품은 2번 위치로, 2번 위치의 상품은 3번 위치로 이동하고, N번 위치의 상품은 1번 위치로 이동한다. k가 0이면 배치는 변하지 않는다. k가 N 이상이어도 같은 규칙을 반복해서 적용한다. 회전하는 동안 상품끼리의 원형 순서는 유지된다. 두 번째는 현재 p번 위치와 q번 위치에 보이는 상품을 서로 바꾸는 작업이다. 이때 위치 번호는 처음 상품이 놓였던 자리를 추적하는 번호가 아니라, 작업 순간에 직원이 바라보는 고정된 위치 번호다. 따라서 앞서 회전 작업이 있었다면 그 회전이 모두 반영된 배치에서 교환해야 한다. p와 q가 같으면 배치는 변하지 않으며, 두 상품의 종류 번호가 같아도 교환 작업은 정상적으로 처리한다. 작업은 입력에 주어진 순서대로 진행하며, 한 작업의 결과는 바로 다음 작업에 반영된다. 모든 작업이 끝난 뒤에는 진열대를 더 회전시키거나 상품을 정렬하지 않는다. 직원이 보는 1번 위치부터 N번 위치까지의 상품 종류 번호를 차례대로 출력한다. 회전 횟수가 매우 클 수 있으므로 실제로 한 칸씩 반복해서 움직이지 않고 최종 배치를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1 ≤ N ≤ 20,000이고, 0 ≤ Q ≤ 20,000이다.
둘째 줄에 초기 배치의 상품 종류 번호 A_1, …, A_N이 주어진다. 모든 A_i는 정수이며 1 ≤ A_i ≤ 9,999이다.
다음 Q개 줄에 작업이 하나씩 주어진다.
R k: 진열대를 시계 방향으로 k칸 회전한다. k는 정수이며 0 ≤ k ≤ 1,000,000,000이다.
S p q: 현재 p번 위치와 q번 위치의 상품을 교환한다. p와 q는 정수이며 1 ≤ p, q ≤ N이다.

출력

모든 작업을 처리한 뒤 1번 위치부터 N번 위치까지의 상품 종류 번호를 공백으로 구분하여 한 줄에 출력한다. Q가 0이면 초기 배치를 그대로 출력한다. 상품은 항상 N개이므로 빈 배치를 출력하는 경우는 없다.

5 3
11 22 33 44 55
R 2
S 1 4
R 1

33 22 55 11 44

3 0
7 7 2

7 7 2

1 3
9
R 1000000000
S 1 1
R 0

9

출처: Devin.KR 자체 제작