Trampoline
hard
PepCoder likes to play with trampolines and add some new flavours to it. This time he has N trampolines in a row from left to right numbered from 1 to N. Each Trampoline has its own jump power(trampoline numbered i has a jump power of pi ). If PepCoder jumps to trampoline i he immediately jumps to trampoline i + pi , then he will jump out of it and so on.If there is no trampoline with such number he falls on the ground and marks the last trampoline he jumped from as bad. U are given Q queries where each query can be of 2 types 0: Set the power of trampoline a to b, 1: Jump to trampoline a and count the number of jumps he makes before falling on the ground and also note down the number of bad trampoline.
Constraints
1 <= Q <= 10 ^5 1 <= N <= 10^5 1 <= a <= N 1 <= b <= 10 ^ 6 a and b are always valid
Format
Input
1: First line contains 2 space separated numbers N and Q, 2: Second line contains N space separated integers p1 p2 p3 ..... pN 3: Next Q lines contains queries of format:- 0 a b 1 a
Output
For each query of type 1 print 2 space separated numbers on a separate line, the number of the bad hole and numbers of jumps PepCoder made before falling to the ground.
Example
Sample Input
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2
Sample Output
8 7
8 5
7 3