E. math problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n.$$$

There is an integer array $$$a$$$ of length $$$n.$$$

We define another array $$$b$$$ of length $$$n$$$ with the following restriction:

For $$$1 \le i \le n,$$$ we have that $$$a_i = \sum_{j=1}^{\lfloor n/i\rfloor} b_{(i\times j)}.$$$

You must support $$$q$$$ queries. The queries can have two types.

1. Update the value of an element of $$$a.$$$

2. Output the value of an element of $$$b.$$$

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1\le n,q\le 2 \cdot 10^5).$$$

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(-10^9\le a_i\le10^9)$$$ — the initial values of $$$a.$$$

Each of the next $$$q$$$ lines contains the queries:

$$$1$$$ $$$i$$$ $$$x$$$ $$$(1\le i\le n,-10^9\le x\le 10^9)$$$ — update the value of $$$a_i$$$ to $$$x.$$$

$$$2$$$ $$$i$$$ $$$(1\le i\le n)$$$ — output the value of $$$b_i.$$$

Output

For each query of the second type, output one integer $$$b_i$$$ on a line.

Examples
Input
5 5
2 4 3 3 2
2 2
1 4 6
2 4
2 2
2 1
Output
1
6
-2
-7
Input
2 3
0 0
1 2 1
2 1
2 2
Output
-1
1