Lostmonkey发明了一种超级反弹装置。为了在绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿一条直线摆放 $n$ 个反弹装置，并按从前往后的方式将反弹装置依次编号为 $0$ 到 $n-1$，对 $0\le i\le n-1$，为第 $i$ 个反弹装置设定了初始弹力系数 $k_i$，当绵羊落到第 $i$ 个反弹装置上时，它将被往后弹出 $k_i$ 步，即落到第 $i+k_i$ 个反弹装置上，若不存在第 $i+k_i$ 个反弹装置，则绵羊被弹飞。绵羊想知道：从第 $i$ 个反弹装置开始，它被弹出几次（含被弹飞的那次）后会被弹飞。为使游戏更有趣，Lostmonkey还可以修改某个反弹装置的弹力系数，但任何时候弹力系数均为正整数。

输入格式

输入第一行是一个整数 $n$，表示地上摆放 $n$ 个反弹装置，输入文件第二行是用空格隔开的 $n$ 个正整数 $k_0,k_1,\ldots,k_{n-1}$，分别表示 $n$ 个反弹装置的初始弹力系数。输入文件第三行是一个正整数 $m$，表示后面还有 $m$ 行输入数据。接下来的 $m$ 行，每行至少有用空格隔开的两个整数 $i$ 和 $j$，若 $i=1$，则你要输出从第 $j$ 个反弹装置开始，被弹出几次后会被弹飞；若 $i=2$，则该行有用空格隔开的三个整数 $i,j$ 和 $k$，表示第 $j$ 个反弹装置的弹力系数被修改为 $k$。

输入的数据保证 20% 的数据满足 $n,m\le 10\,000$。100% 的数据满足 $n\le 200\,000,m\le 100\,000$。

输出格式

输出包含的行数等于输入文件最后 $m$ 行中 $i=1$ 的行数。

第 $h$ 行输出一个整数，表示对输入中给出的第 $h$ 个求弹出次数的问题，基于 $n$ 个反弹装置当时的弹力系数，求出的弹出次数。

样例数据

输入样例

4
1 2 1 1
3
1 1
2 1 1
1 1

输出样例

2
3