P1483 Sequence Transformation

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$.

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 several lines, each corresponding to one operation 2.

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