31563번 - 수열 회전과 쿼리

문제

길이가 $N$인 정수 수열 $[A_1,A_2,\dots,A_N]$이 주어진다. 이때 다음 쿼리를 수행하는 프로그램을 작성해보자.

• 1ドル$ $k$: 수열을 오른쪽으로 $k$만큼 회전시킨다. 즉, $A_1$의 값은 $A_{N-k+1},ドル $A_2$의 값은 $A_{N-k+2},ドル $\dots,ドル $A_k$의 값은 $A_N,ドル $A_{k+1}$의 값은 $A_1,ドル $A_{k+2}$의 값은 $A_2,ドル $\dots,ドル $A_N$의 값은 $A_{N-k}$로 동시에 변한다.
• 2ドル$ $k$: 수열을 왼쪽으로 $k$만큼 회전시킨다. 즉, $A_1$의 값은 $A_{k+1},ドル $A_2$의 값은 $A_{k+2},ドル $\dots,ドル $A_{N-k}$의 값은 $A_N,ドル $A_{N-k+1}$의 값은 $A_1,ドル $A_{N-k+2}$의 값은 $A_2,ドル $\dots,ドル $A_N$의 값은 $A_k$로 동시에 변한다.
• 3ドル$ $a$ $b$: 수열의 $a$번째 수부터 $b$번째 수의 합을 출력한다. 즉, $\sum_{i=a}^b A_i$를 출력한다.

입력

첫 번째 줄에 수열의 길이 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $A_1,A_2,\dots,A_N$이 공백으로 구분되어 주어진다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

출력

3ドル$번 쿼리에 대한 결괏값을 한 줄에 하나씩 입력으로 주어진 순서대로 출력한다.

제한

• 2ドル \le N \le 200,000円$
• 1ドル \le Q \le 200,000円$
• 1ドル \le A_i \le 10^9$
• 1ドル \le k \le N$
• 1ドル \le a \le b \le N$
• 입력으로 주어지는 모든 수는 정수이다.
• 3ドル$번 쿼리는 한 번 이상 주어진다.

노트