Problem F
Modulo Data Structures

You have an array, $Arr[1...N]$. Initially, all values of $Arr[i] = 0$. The array supports the following two types of queries:

1. Increase all $Arr[k]$ by $C$ for all $k\equiv A\ (\mathrm{mod}$ $B)$;

2. Output $Arr[D]$ for a given $D$.

Input

The first line of input consists of two integers, $N$ and $Q$, representing the length of the array and the number of queries, respectively. Note that $1 \leq N,Q \leq 200\, 000$.

The following $Q$ lines all begin with an integer $T$ representing the type of query. If $T = 1$, then it will be followed by three integers representing $A$, $B$ and $C$ respectively. Note that $1 \leq C \leq 10\, 000$, $0 \leq A < B \leq N$. Else, $T$ will be $2$, and it will be followed by one integer representing $D$, subjected to $1 \leq D \leq N$.

Output

For each query of type $2$, output the integer value of $Arr[D]$ on a separate line.

5 10
1 1 2 7
1 4 5 6
1 2 3 3
2 1
2 2
2 3
1 3 4 3
2 3
2 4
2 5

7
3
7
10
6
10