#P1483. 序列变换

序列变换

题目描述

给定一个由 nn 个整数构成的序列 a1,a2,,ana_1, a_2, \ldots , a_n,你需要对它进行如下操作:

  1. 输入格式 1 x y,表示把所有 akxa_{k x}kk 为正整数,kxnk x \le n)都加上 yy
  2. 输入格式 2 j,表示输出 aja_j

输入格式

第一行,两个数 n,mn, m,表示有 nn 个数,mm 条操作。
第二行,nn 个数 a1,a2,,ana_1, a_2, \ldots , a_n
接下来 mm 行,为 mm 条操作。

输出格式

输出若干行,每行对应一次操作2。

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

提示

对于 40%40 \% 的数据,n100n \le 100
对于 100%100 \% 的数据,1n1061 \le n \le {10}^61m1051 \le m \le {10}^5ai106|a_i| \le {10}^6y106|y| \le {10}^61x,jn1 \le x, j \le n,操作 2 不超过 104{10}^4 条。