B. Arcade Game
time limit per test
5 seconds
memory limit per test
512 МБ
input
standard input
output
standard output

On Valentine's Day, Bob and Alice decided to spend a fun afternoon at the arcade, indulging in a variety of games. Among them was a quirky game centered around the summation of numbers. Being the curious nerd that he is, Bob eagerly stepped up to the challenge, determined to conquer the game and claim the prize. The game consists of an array of $$$n$$$ zeros and $$$q$$$ queries that you should apply/answer correctly; each query is one of the $$$2$$$ types:

  • $$$1$$$ $$$l$$$ $$$r$$$ : write the sum of elements from $$$l$$$ to $$$r$$$ in the array
  • $$$2$$$ $$$l$$$ $$$r$$$ $$$p$$$ $$$k$$$ $$$v$$$ : Add $$$v$$$ to every index $$$i$$$ such that $$$l\leq i \leq r$$$ and $$$i \% p=k$$$ (the remainder of division of $$$i$$$ by $$$p$$$ is equal to $$$k$$$)
Can you help Bob beat the game ?
Input

The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ $$$(1 \leq n,q \leq 2.10^{5})$$$.

The next $$$q$$$ lines each contain one query of $$$2$$$ types:

  • $$$1$$$ $$$l$$$ $$$r$$$ $$$(1\leq l \leq r \leq n)$$$
  • $$$2$$$ $$$l$$$ $$$r$$$ $$$p$$$ $$$k$$$ $$$v$$$ $$$(1 \leq l \leq r \leq n, 1 \leq v \leq 10^{5}, 1 \leq p \leq 5, 0 \leq k \lt p)$$$

It is guaranteed that there is at least a query of type $$$1$$$ in the input.

Output

Print the answers for the queries of the first type.

Example
Input
5 7
2 1 5 2 1 5
2 1 3 1 0 2
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
Output
7
2
7
0
5