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$번 쿼리는 한 번 이상 주어진다.