Problem B
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:
-
Increase all $Arr[k]$ by $C$ for all $k\equiv A\ (\mathrm{mod}$ $B)$;
-
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.
Sample Input 1 | Sample Output 1 |
---|---|
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 |