Sequence Rotation and Queries

An integer sequence $A_1, A_2, \dots, A_N$ of length $N$ is given. Write a program that handles the following queries.

• $1$ $k$: Rotate the sequence to the right by $k$. The value of $A_1$ becomes $A_{N-k+1}$, $A_2$ becomes $A_{N-k+2}$, $\dots$, $A_k$ becomes $A_N$, $A_{k+1}$ becomes $A_1$, $A_{k+2}$ becomes $A_2$, $\dots$, and $A_N$ becomes $A_{N-k}$. All values change at the same time.
• $2$ $k$: Rotate the sequence to the left by $k$. The value of $A_1$ becomes $A_{k+1}$, $A_2$ becomes $A_{k+2}$, $\dots$, $A_{N-k}$ becomes $A_N$, $A_{N-k+1}$ becomes $A_1$, $A_{N-k+2}$ becomes $A_2$, $\dots$, and $A_N$ becomes $A_k$. All values change at the same time.
• $3$ $a$ $b$: Print the sum of the $a$-th through $b$-th numbers, that is, $\sum_{i=a}^b A_i$.

The first line contains $N$ and $Q$, separated by a space. The second line contains $N$ integers $A_1, A_2, \dots, A_N$, separated by spaces. The next $Q$ lines each contain one query.

For each type 3 query, print the result on its own line, in the order the queries are given.

• $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$
• Every number in the input is an integer.
• At least one type 3 query is given.