Problem E
Hringvegurinn

Vegagerðin is renewing the software they use to track maintenance and repair costs for roads. The first step towards that is implementing the new system for the most important road in the country, hringvegurinn. To simplify things, the circular road is divided into $N$ equally long sections and they are numbered $1, 2, \dots , N$ where $1$ is the road heading west from Akureyri and the sections are in increasing order following that one going around the country. Then section $N$ is the section of road east of Akureyri. The system needs to support the following operations. It needs to be possible to register a cost $x$ for each section in an interval. It needs to be possible to get the total cost for an interval thus far. Finally the system has to be able to rotate the numbering such that section $1$ is in a new location. An interval means a contigious section of the road. The interval $3, 6$ contains the sections $3, 4, 5, 6$. However, if $N = 6$ the interval $5, 2$ contains the sections $5, 6, 1, 2$. The interval $3, 3$ is just the section $3$. After relabeling the sections the orientation is still the same, so the sections are still increasing when traveling counter-clockwise. Rotating by $1$ section means that the section numbered $1$ will be numbered $N$ and section numbered $2$ will be numbered $1$.

Input

The first line of the input contains two integers, the number of sections $N$ and the number of queries $q$ ($1 \leq N \leq 10^6$, $1 \leq q \leq 10^4$). Next there are $q$ lines, each with one query. Each query is a single line and starts with the number $1, 2$ or $3$. If it starts with $1$ there will follow a single number $t$ ($1 \leq t \leq N$) which means the numbering should be rotated cyclically by $t$ sections counter-clockwise. If the query starts with the number $2$ there will follow three integers $l, r, x$ ($1 \leq l, r \leq N$, $1 \leq x \leq 10^9$) which means that the total cost on the sections from $l$ to $r$ should each be increased by $x$. Finally if the query starts with the number $3$ there will follow two integers $l, r$ ($1 \leq l, r \leq N$) in which case the total cost of the sections from $l$ to $r$ should be printed.

Output

One line for each query starting with the number $3$ should be printed as described above.

Scoring

Group	Points	Constraints
1	20	$1 \leq n \leq 1000$
2	50	$l \leq r$ in all intervals and there are no rotation operations
3	30	No further constraints

Sample Input 1	Sample Output 1
10 10 2 2 4 3 2 3 3 4 3 3 4 3 4 2 1 1 2 4 1 7 3 1 3 1 5 3 10 1 3 2 2	10 6 20 14 7