Migrated from Lutece 1344 卿学姐种美丽的花

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，在喵哈哈村，有一个温柔善良的卿学姐。

卿学姐喜欢和她一样美丽的花。所以卿学姐家的后院有很多的花坛。

卿学姐有$n$个花坛，一开始第$i$个花坛里有$A[i]$朵花。每过一段时间，卿学姐都会在花坛里种上新的花。

作为一个聪明的学姐，卿学姐的种花方式也是与众不同 , 每一次，卿学姐会在第$x$个花坛种上$y$朵花，然后在第$x+1$个花坛上种上$y-1$朵花，再在第$x+2$个花坛上种上$y-2$朵花......以此类推，直到种到最后一个花坛，或者不需要种花为止。

喵哈哈的村民们都喜欢去卿学姐的后院赏花，沈宝宝也不例外。然而沈宝宝可不是省油的灯，怎么可能会老老实实地赏花呢。每次沈宝宝来时，都会随机询问卿学姐在第$i$个花坛有多少朵花。

花坛的花实在太多了，卿学姐实在是数不过来。于是现在她向你求助，希望你能帮她数出花坛里多少朵花。

Input

第一行输入两个整数，花坛个数$N$和操作次数$Q$。

第二行$N$个整数$A[1],A[2],A[3].....A[N]$。 ( $1 \leq A[i] \leq 2^{31}$ )

接下来$Q$行，每行一个操作。

1. 1 x y 表示卿学姐会在$x$号花坛种$y$朵花，并按相应的规律在后面的花坛上种花。

2. 2 x 表示沈宝宝问卿学姐第$x$个花坛有多少朵花。

数据保证:

• $1 \leq N \leq 10^6$

• $1 \leq Q \leq {2*10^6}$

• 对于操作 $1$ , $1 \leq x \leq N$，$1 \leq y \leq 10^9$

• 对于操作 $2$ , $1 \leq x \leq N$

Output

对于每个询问操作，按顺序输出答案对$772002 + 233$取模的值。

Samples

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

5
2

Resources

2016 UESTC Training for Data Structures