Little Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:

There are N holes located in a single row and numbered from left to right with numbers from 1 to N. Each hole has it's own power (hole number i has the power ai). If you throw a ball into hole i it will immediately jump to hole i + ai, then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the M moves the player can perform one of two actions: 

  * Set the power of the hole a to value b. 
  * Throw a ball into the hole a and count the number of jumps of a ball before it jump out of the row and also write down the number of the hole from which it jumped out just before leaving the row. 



Petya is not good at math, so, as you have already guessed, you are to perform all computations.

Input

The first line contains two integers N and M (1 ≤ N ≤ 105, 1 ≤ M ≤ 105) — the number of holes in a row and the number of moves. The second line contains N positive integers not exceeding N — initial values of holes power. The following M lines describe moves made by Petya. Each of these line can be one of the two types: 

  * 0 a b
  * 1 a

Type 0 means that it is required to set the power of hole a to b, and type 1 means that it is required to throw a ball into the a-th hole. Numbers a and b are positive integers do not exceeding N.

Output

For each move of the type 1 output two space-separated numbers on a separate line — the number of the last hole the ball visited before leaving the row and the number of jumps it made.

Examples

Input

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


Output

8 7
8 5
7 3
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.*;


public class Main {

	static int numHoles,numQueries,numBlocks,blockSize;
	static PrintWriter pw;
	static int[] next,blockNo,hopCount,jumpLength;
	static int temp = 0 ;
	
	public static void main( String args[]) throws Exception{
		
	
/*		BufferedReader br = new BufferedReader( new InputStreamReader(System.in),8*1024);
		Scanner sc = new Scanner(br);
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out),8*1024);
		pw = new PrintWriter(bw );
	*/
		
		NewScanner ns = new NewScanner();
		ns.init();
		
		numHoles = ns.nextInt();
		numQueries = ns.nextInt();
	
		
		next = new int[numHoles];
		blockNo = new int[numHoles];
		hopCount = new int[numHoles];
		jumpLength = new int[numHoles];

		
		blockSize = (int)Math.sqrt(numHoles);
		numBlocks = (numHoles+blockSize-1)/blockSize;
		
		for( int i = 0 ; i < numHoles ; ++i ){
			
			jumpLength[i] = ns.nextInt();
			//blockNo[i] = i/blockSize;
		}
		
		
		int blockNum = -1 ;
		for( int i = 0 ; i < numHoles ; ++i){
			if( i % blockSize == 0 ) blockNum++;
			blockNo[i] = blockNum;
		}
		
		
		
		for( int i = 0 ; i < numHoles ; ++i ){
			
			if( hopCount[i] == 0 )
				initiate(i);
		}
		
		int type = 0 ;
		int index,newJumpLength,bNo,count,current,last;
		
		while( numQueries-- > 0 ){
			
			type = ns.nextInt();
			
			if( type == 0 ){
				
				index = ns.nextInt() - 1;
				newJumpLength = ns.nextInt();
				bNo = blockNo[index];
				jumpLength[index] = newJumpLength;
				
				for( int j = Math.min( blockSize*(bNo+1), numHoles )-1 ; j >= blockSize*bNo ; --j ){
					initiate( j);
					
				}
			}
			
			else{
				
				
				count = 0 ; 
				
				current = ns.nextInt()-1;
				
				count += hopCount[current];
				
				while( (temp = next[current]) < numHoles){
					
					current = temp;
					count += hopCount[current];
					
				}
				
				last = current;
				
				while( (temp = last + jumpLength[last]) < numHoles ){
					last = temp;
				}
			
				ns.println((last+1) + " " + count);
			}
		}
		
		ns.destroy();
	}
	
	static void initiate(int current  ){
		
	
		int next = current + jumpLength[current];
			
		if( (next >= numHoles) ){
			hopCount[current] = 1 ; 
			Main.next[current] = numHoles;
			
			return ; 
		}
		
		
		
		if( (blockNo[next] !=  blockNo[current]) ){ // in next block now
			hopCount[current] = 1 ; 
			Main.next[current] = next;
			
		}
			
		else {// same block , already visited
			
			if( hopCount[next] == 0 )
				initiate(next);
			
			hopCount[current] = 1+hopCount[next];
			Main.next[current] = Main.next[next];
				
		}
			
	}
	
		
	
	
	
	static long lcm( long a , long b ){
		
		return (a*b)/gcd(a,b);
		
	}

	static long gcd( long a , long b ){
		
		if( a == 0 ) return b ; 
		if( b == 0 ) return a;
		if( b > a ) return gcd(a,b%a);
		else return gcd( b , a%b );
	}
	
	static class MyScanner {
	      BufferedReader br;
	      StringTokenizer st;
	 
	      public MyScanner() {
				br = new BufferedReader( new InputStreamReader(System.in) ,8*1024);
	      }
	 
	      String next() {
	          while (st == null || !st.hasMoreElements()) {
	              try {
	                  st = new StringTokenizer(br.readLine());
	              } catch (IOException e) {
	                  e.printStackTrace();
	              }
	          }
	          return st.nextToken();
	      }
	 
	      int nextInt() {
	          return Integer.parseInt(next());
	      }
	 
	      long nextLong() {
	          return Long.parseLong(next());
	      }
	 
	      double nextDouble() {
	          return Double.parseDouble(next());
	      }
	 
	      String nextLine(){
	          String str = "";
		  try {
		     str = br.readLine();
		  } catch (IOException e) {
		     e.printStackTrace();
		  }
		  return str;
	      }

	   }

	static class MyWriter 
{
	    BufferedWriter bw;

	    public  MyWriter() {
	       bw = new BufferedWriter(new OutputStreamWriter(System.out),8*1024);
	    }

	    void print(String s)
	    {
	    	try {
				bw.write( s , 0 , s.length() );
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	    }
	    
	    void println(String s)
	    {
	    	try {
				bw.write( s , 0 , s.length() );
				bw.newLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	    }

	 void close()
	 {
		 try {
			bw.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	 }
	}
	
	
	static class NewScanner{
		
		
		BufferedReader reader;
		StringTokenizer tokenizer;
		PrintWriter writer;

		public void init() {
			try {
				reader = new BufferedReader(new InputStreamReader(System.in));
				writer = new PrintWriter(System.out);
			} catch (Exception e) {
				e.printStackTrace();
				System.exit(261);
			}
		}

		void destroy() {
			writer.close();
			System.exit(0);
		}

		void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		void println(Object... objects) {
			print(objects);
			writer.println();
		}

		String nextLine() throws IOException {
			return reader.readLine();
		}

		String nextToken() throws IOException {
			while (tokenizer == null || !tokenizer.hasMoreTokens())
				tokenizer = new StringTokenizer(nextLine());
			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(nextToken());
		}
	}

}

/*
 * 
 * 
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2

8 7
8 5
7 3


---------------------------
10 1 9 4 16  X 
1 2 1 1 1  X 
20 20 20 20 20 
17
------------------------------------
*/
