description

猫猫头收到了一个开学礼物，一个由$n$个数字组成的数组a，现在猫猫头将进行$m$次操作，每次操作有两种情况

1. 在数组的最后添加一个数$x (0 \le x \le 10^9)$，使数组的长度增加一。

2. 数组$a$第$i$个数字$a_i$增加$y (0 \le y \le 10^9),i (1 \le i \le |a|)$ $|a|$表示的是$a$数组的长度

在每次操作后输出数组中最小的数$\% 1000000007$

input

输入的第一行有两个数$n,m$ -- 代表数组的初始长度和操作次数

输入的第二行包括$n (1 \le n \le 2 \cdot 10^5)$个数字，分别是$a_1 ... a_n$

接下来一共$m (1 \le m \le 2 \cdot 10^5)$行，每行的第一个数字$t$代表操作的种类

如果$t=1$，该行后面有一个数字$x (0 \le x \le 10^9)$，代表在数组的最后添加一个数$x$.

如果$t=2$，该行后面有两个个数字$i (1 \le i \le |a|$，$|a|$表示的是$a$数组的长度$)$,$x (0 \le x \le 10^9)$,这代表第$i$个数字加上$x$.

output

输出$m$行，每次操作输出一行，每行一个数字，当前数组最小的数字$\%1000000007$

Sample Input:

5 5
1 2 3 4 5
1 6
1 7
2 1 3
2 2 5
1 1

Sample Output:

1
1
2
3
1