VATRAXIA

Problem

The FrogLab at NTUA constructs genetically modified frogs for rescue missions in lakes. To guide the rescue frogs to the rescue point, lily pads of different elasticity are placed in a row. Specifically, there are ~N~ arranged lily pads and the ~i~-th one has elasticity ~a_i~. If a frog is placed on lily pad ~i~, it will make a jump of length ~a_i~ and land on lily pad ~j = i + a_i~. It will then make a jump of length ~a_j~ and land on lily pad ~j + a_j~, and so on. When ~j + a_j~ exceeds ~N~, we consider that the frog has passed the sequence of lily pads and reached the rescue point.

The lab's testing team is interested in experimentally evaluating the effectiveness of the modified frogs. For this purpose, they conduct a series of ~Q~ experiments, each of which can be in one of the following two forms:

• ~0\;p\;x~
• ~1\;p~

In form ~0~, the scientists replace the lily pad at position ~p~ with another one of elasticity ~x~, i.e., they set ~a_p = x~.

In form ~1~, they release a frog on lily pad ~p~ and count the number of jumps it makes until it reaches the rescue point, as well as the lily pad from which the last jump was made.

The lab's testing team assigns you the task of simulating this process. Specifically, you are given the initial elasticities for the ~N~ lily pads as well as the ~Q~ experiments to be performed. Your goal is to successfully execute all ~Q~ experiments, and for each experiment of form ~1~, to print the last lily pad the frog passes through and the total number of jumps it makes.

Input:

In the first line of the input, there will be a positive integer ~T~, the number of test cases. In each of the next ~T~ test cases, the first line will contain two non-negative integers ~N~ and ~Q~: the number of lily pads and the number of experiments to be performed. The second line contains ~N~ positive integers ~a_1~, ~a_2~, ~...~, ~a_N~ that indicate the initial elasticities for the ~N~ lily pads. Finally, the next ~Q~ lines of the input each contain one experiment, in one of the forms mentioned above.

Output:

The output should contain as many lines as there are type ~1~ experiments in total. Each line will contain two numbers indicating the lily pad from which the last jump was made and the number of jumps until the frog in the corresponding type ~1~ experiment reaches the rescue point.

Constraints

• ~1 \le N \le 100.000~
• ~1 \le Q \le 100.000~
• The total sum of all ~N~ will not exceed ~200.000~. Similarly for Q.
• At any given time, ~1 \le a_i \le 100.000~ for each ~i~.
• Time Limit: ~1~ sec.
• Memory Limit: ~64~ MB.

Example of Input - Output Files:

STDIN (vatraxia.in)

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

STDOUT (vatraxia.out)

8 7
8 5
7 3

Explanation of the example

In the first and only test case of the example, there are ~8~ lily pads with initial elasticities as shown in the ~3rd~ line. There are ~5~ experiments.

• In the ~1st~ experiment, we release a frog on lily pad ~1~. This frog follows the path (~1~, ~2~, ~3~, ~4~, ~5~, ~6~, ~8~) before reaching the rescue point. Therefore, the ~1st~ output line contains ~8~, which is the last lily pad it passes, and ~7~, which is the number of jumps it made.
• In the ~2nd~ experiment (which is of type ~0~), we change the elasticity of lily pad ~1~ to the value ~3~.
• In the ~3rd~ experiment, we release another frog on lily pad ~1~. This time, lily pad ~1~ has an elasticity of ~3~ instead of ~1~, so the path the frog follows is (~1~, ~4~, ~5~, ~6~, ~8~). Again, the last lily pad is ~8~, but now it took ~5~ jumps. Therefore, we print ~8~ ~5~ in the second output line.
• In the ~4th~ experiment, we change the elasticity of lily pad ~3~ to the value ~4~.
• In the ~5th~ experiment, we release a frog on lily pad ~2~. It follows the path (~2~, ~3~, ~7~), so it takes ~3~ jumps, and the last lily pad it passes is ~7~. Therefore, we print ~7~ ~3~ in the last output line.

Notes

• For test cases with a total value of ~20%~, it will be ~1 \le N \le 1000~, ~1 \le Q \le 1000~, and the total sum of ~N~ in each test file will not exceed ~2000~. The same applies to ~Q~.
• For test cases with a total value of ~20%~, the initial constraints will hold, and additionally, there will only be type ~1~ experiments in the input.