Description

Given a sequence of $n$ integers $a_1, a_2, \ldots , a_n$, you need to perform the following operations:

1. Input format 1 x y, which means add $y$ to all $a_{k x}$ (where $k$ is a positive integer and $k x \le n$).
2. Input format 2 j, which means output $a_j$.

Specifically, for operation 2, when $j = 0$, output $0$.

Input Format

The first line contains two integers $n, m$, meaning there are $n$ numbers and $m$ operations.
The second line contains $n$ integers $a_1, a_2, \ldots , a_n$.
Then follow $m$ lines, each describing one of the $m$ operations.

Output Format

Output several lines, each corresponding to one operation 2.

5 4
6 9 9 8 1 
2 4
1 2 5
1 3 1
2 4

8
13

Hint

For $40 \%$ of the testdata, $n \le 100$.
For $100 \%$ of the testdata, $1 \le n \le {10}^6$, $1 \le m \le {10}^5$, $|a_i| \le {10}^6$, $|y| \le {10}^6$, $1 \le x\le n$, $0\le j \le n$, and the number of operation 2 is at most ${10}^4$.

Translated by ChatGPT 5