원형 택배 선반

문제

택배 분류실에는 N개의 칸이 원형으로 이어진 선반이 있다. 각 칸에는 택배가 정확히 하나씩 놓여 있다. 작업자는 선반 앞의 고정된 기준선에서 시작하여 시계 방향으로 칸을 세고, 그 순서대로 현재 위치 번호 1부터 N을 붙인다. 위치 번호는 선반에 적힌 고유 번호가 아니라 기준선에서 바라본 현재 순서를 뜻한다. 따라서 선반이 회전하면 같은 택배의 위치 번호가 달라질 수 있다. 작업 기록에는 두 종류의 명령이 들어 있다. R k는 선반을 시계 방향으로 k칸 회전시키는 명령이다. 이 회전은 기존 위치 N의 택배가 위치 1로 이동하는 변화를 한 칸 회전으로 정의한다. 따라서 한 칸 회전한 뒤 기존 위치 1의 택배는 위치 2에 놓인다. k가 N 이상일 수도 있으며, N칸 회전하면 모든 택배가 회전 전과 같은 위치로 돌아온다. k가 0이면 아무 변화도 없다. S a b는 명령을 실행하는 시점의 위치 a와 위치 b에 놓인 택배를 서로 바꾸는 명령이다. a와 b가 같으면 선반의 상태는 변하지 않는다. 교환을 위해 선반을 추가로 회전시키지는 않는다. 이전 회전 명령으로 위치가 바뀌었다면 그 결과를 반영한 위치의 택배를 교환해야 한다. 택배에는 양의 정수인 분류 표식이 붙어 있다. 서로 다른 택배에 같은 표식이 붙을 수 있으므로 표식이 같다는 이유로 택배를 하나로 합치거나 제거하지 않는다. 모든 명령은 입력에 주어진 순서대로 정확히 한 번씩 실행한다. 명령을 모두 실행한 뒤 기준선에서 시작하여 시계 방향으로 읽은 분류 표식을 구하는 프로그램을 작성한다. 명령이 하나도 없다면 처음에 주어진 순서가 그대로 결과가 된다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1≤N≤10,000, 0≤Q≤10,000이다.
둘째 줄에 초기 위치 1부터 N까지의 분류 표식 A_1,…,A_N이 주어진다. 각 표식은 1 이상 1,000,000,000 이하의 정수다.
다음 Q개 줄에 명령이 하나씩 주어진다. 명령은 R k 또는 S a b 형식이다. k,a,b는 정수이며 0≤k≤1,000,000,000, 1≤a,b≤N이다.

출력

모든 명령을 실행한 뒤 현재 위치 1부터 N까지의 분류 표식을 공백으로 구분하여 한 줄에 출력한다.

5 3
10 20 30 40 50
R 2
S 1 4
R 1

30 20 50 10 40

1 4
7
R 1000000000
S 1 1
R 0
S 1 1

7

4 0
8 8 2 8

8 8 2 8

출처: Devin.KR 자체 제작