수열 회전과 쿼리

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