UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4764. 弹飞大爷

统计 下载数据

Description

自从WC退役以来,大爷是越来越懒惰了。为了帮助他活动筋骨,也是受到了弹飞绵羊一题的启发,机房的小伙伴们
决定齐心合力构造一个下面这样的序列。这个序列共有N项,每项都代表了一个小伙伴的力量值,如果大爷落到了
第i个小伙伴的手里,那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里,其中ai就是第i个小伙伴的力量值,也
就是序列的第i项。然而,因为大爷太沉了,所以有些小伙伴不能撑到锻(you)炼(xi)结束,所以我们中途会替
换一些小伙伴,也就是改变序列的某些项。而且,因为大爷太沉了,所以有些小伙伴不能把大爷扔向前方,而是会
把大爷往反方向扔,也就是序列中的一些项会是负的(当然,也可能是零喽)。现在机智的大爷通过在空中的观察
,已经知道小伙伴们的所有活动——即初始序列、所有更改操作,他想请你算一算,如果他在某时刻落到了某个位
置,那么他会在几次弹起之后落到小伙伴序列之外(毕竟摔在地上还是蛮疼的)。

Input

第一行为两个整数N和M,代表序列长度和操作次数。
第二行为N个整数,代表初始的小伙伴序列。
接下来有M行,每行代表一个操作。
如果这一行的第一个数是1,代表该操作是一个询问操作,接下来一个数X,代表询问此时大爷从X处,经过几次弹
起会摔在地上。如果永远不会摔在地上,请输出-1。
如果这一行的第一个数是2,代表该操作是一个更改操作,接下来两个数X,Y,代表将序列的第X项改为Y。
N,M <= 200000  |Ai| < N

Output

对于每次询问操作,输出弹起次数或-1。

Sample Input

3 19
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3

Sample Output



3
2
1
2
2
1
-1
-1
-1
3
1
2
3
1
2

Hint

Source

By YouSiki & GuoZZ