Given a one-indexed array ~a~ of ~N~ elements, support the following operations:

• 1 k v Add ~v~ to all elements with indices that are a multiple of ~k~ ~(1 \le v \le 10^9, 2 \le k \le N)~. ~k~ is prime.
• 2 i Output the value of the element at index ~i~ ~(1 \le i \le N)~.

There will be ~Q~ of these operations.

Input Specification

The first line will contain ~2~ integers, ~N, Q~ ~(2 \le N \le 2 \times 10^5, 1 \le Q \le 2 \times 10^5)~.

The next ~Q~ lines will each contain a valid operation as described above.

Output Specification

For each type ~2~ operation, output the value as defined above.

Sample Input

6 4
1 2 2
2 4
1 3 1
2 6

Sample Output

2
3