회전 선반의 우편함

문제

우체국의 분류 작업대에는 우편물 보관함 N개가 원형 선반에 놓여 있다. 작업자는 선반 앞에 고정된 표시판을 두고, 표시판의 왼쪽부터 오른쪽까지 보이는 자리를 1번부터 N번까지라고 부른다. 각 자리에는 보관함 하나가 있으며, 보관함에 적힌 수는 그 안에 들어 있는 우편물의 개수다. 처음 각 자리에 놓인 보관함의 우편물 개수가 주어진다. 작업 중에는 선반을 회전하거나 한 보관함의 우편물 개수를 새로 기록한다. 회전 명령 R k에서 k가 양수이면 모든 보관함을 자리 번호가 증가하는 방향으로 k칸 이동한다. N번 자리 다음은 1번 자리다. k가 음수이면 반대 방향으로 -k칸 이동하며, 1번 자리 이전은 N번 자리다. k가 0이면 아무것도 이동하지 않는다. 회전할 때 보관함 속 우편물 개수는 바뀌지 않는다. 기록 명령 P i v는 명령을 실행하는 시점에 i번 자리에 있는 보관함의 우편물 개수를 v로 바꾼다. 기존 값에 v를 더하는 명령이 아니다. i는 처음 보관함에 붙인 번호가 아니라 고정된 표시판의 자리 번호이므로, 앞서 실행한 회전에 따라 수정되는 보관함이 달라질 수 있다. 모든 명령은 입력된 순서대로 하나씩 실행한다. 한 바퀴 이상 회전하는 명령도 같은 규칙을 적용하며, 보관함이 하나뿐인 경우에는 어떤 회전도 자리의 상태를 바꾸지 않는다. 우편물이 없는 보관함은 0으로 나타내며, 기록 후에도 해당 보관함은 선반에 남아 있다. 마지막 명령까지 실행했을 때 1번 자리부터 N번 자리까지의 우편물 개수를 차례대로 구한다. 명령이 하나도 없다면 처음 주어진 배열을 그대로 출력한다.

입력

첫째 줄에 정수 N과 Q가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ Q ≤ 20,000이다.
둘째 줄에 처음 1번 자리부터 N번 자리까지의 우편물 개수 A_1, ..., A_N이 주어진다. 각 값은 0 이상 999 이하의 정수다.
다음 Q개 줄에는 명령이 하나씩 주어진다. 회전 명령은 R k 형식이며 k는 -100,000 이상 100,000 이하의 정수다. 기록 명령은 P i v 형식이며 i와 v는 정수이고 1 ≤ i ≤ N, 0 ≤ v ≤ 999이다.

출력

모든 명령을 실행한 뒤 각 자리의 우편물 개수를 1번 자리부터 순서대로 한 줄에 공백으로 구분하여 출력한다.

4 3
10 0 30 40
R 1
P 3 7
R -2

7 30 40 10

1 2
8
P 1 0
R -5

0

3 0
2 2 0

2 2 0

출처: Devin.KR 자체 제작