Arithmetic Progression Addition

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$ which is initially all $0$.

You need to support $q$ operations:

1. 1 x y d: add $d$ to every position $i$ with $i \equiv y \pmod x$.
2. 2 x: point query the value of $a_x$.

Input Format

The first line contains two integers $n, q$ ($1\leq n, q\leq 2\times 10^5$).

The next $q$ lines each describe an operation, with $1\leq x\leq n, 0\leq y < x, 1\leq d\leq 10^9$ guaranteed.

Output Format

For each query operation, output one number, the answer.

Sample Input

5 6
1 2 1 3
1 3 2 5
2 3
2 5
1 5 0 6
2 5

Sample Output

3
8
14