← 返回题目列表

Codeforces · 13/E

E. 孔

中文机器翻译题面 查看原题

小 Petya 很喜欢玩。他最喜欢玩“Holes”游戏。这是一款单人游戏,规则如下:

单行有 N 个孔,从左到右编号为 1 到 N。每个孔都有自己的功率(编号 i 的孔具有功率 ai)。如果你把一个球扔进第i个洞,它会立即跳到第i个洞+ai,然后它会跳出洞,依此类推。如果没有这个数字的洞,球就会跳出该行。在 M 次移动中,玩家可以执行以下两个操作之一:

- 将孔 a 的功率设置为值 b。
- 将一个球扔进a洞,数一下球跳出该行之前的跳跃次数,并记下它在离开该行之前跳出的洞号。

Petya 不擅长数学,因此,正如您已经猜到的那样,您将执行所有计算。

输入

第一行包含两个整数 N 和 M (1 ≤ N ≤ 105, 1 ≤ M ≤ 105) — 一行中的洞数和移动次数。第二行包含N个不超过N的正整数——空穴功率的初始值。以下 M 行描述了 Petya 的动作。每条线都可以是以下两种类型之一:

- 0 a b
- 1 个

输出

对于类型 1 的每次移动,在单独的行上输出两个空格分隔的数字 - 球离开该行之前访问的最后一个洞的号码以及它进行的跳跃次数。

示例

输入 #1

8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2

输出 #1

8 7
8 5
7 3