수열 회전과 쿼리

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