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.DataInputStream;
	import java.io.FileInputStream;
	import java.io.IOException;
	import java.util.*;
	
	
	
	public class test {
	
    	static int mod = (int) 1e9 + 7;
    	static ArrayList<Integer> gr[];
    	static int ar[];
    	static Reader sc = new Reader();
    	static int pri[] = new int[(int) 1e6 + 5];
    	static StringBuilder out = new StringBuilder();
     
    	public static class pair implements Comparable<pair> {
    		int id;
    		int ans;
     
    		pair(int x, int y) {
     
    			id = x;
    			ans = y;
     
    		}
     
    		public pair() {
     
    		}
     
    		public int compareTo(pair o) {
    			// TODO Auto-generated method stub
     
    			return this.id - o.id;
    		}
    	}
     
    	static void forl(int[] a, int s, int e) throws IOException {
    		for (int i = s; i < e; i++) {
    			a[i] = sc.nextInt();
    		}
    	}
     
    	static class query implements Comparable<query> {
    		int id, l, r;
     
    		query(int id, int l, int r) {
    			this.id = id;
    			this.l = l;
    			this.r = r;
    		}
     
    		@Override
    		public int compareTo(query o) {
    			// TODO Auto-generated method stub
    			if (this.l / block == o.l / block)
    				return this.r - o.r;
    			return this.l / block - o.l / block;
    		}
     
    	}
     
    	static int block=300;
    	static long ans = 0;
    	static int[] cnt;
     
    	static void update(int l,int r,int a) {
    		
    		
    		for(int i=a;i>=l;i--) {
    			
    			if(i+ar[i]>=r || i+ar[i]>=ar.length ) {
    				next[i]=i+ar[i];
    				cnt[i]=1;
    			}
    			else {
    				next[i]=next[i+ar[i]];
    				cnt[i]=1+cnt[i+ar[i]];
    			}
    		}
    		
    		
    	}
    	static int next[];
    	public static void main(String[] args) throws IOException {
     
    		int t = 1;// sc.nextInt();
    		while (t-- > 0) {
     
    			int n = sc.nextInt();
    			int q = sc.nextInt();
     
    			ar = new int[n];
    			for (int i = 0; i < n; i++) {
    				ar[i] = sc.nextInt();
    			}
    			
    			block=300;//(int) Math.sqrt(n)+1;
    			 next=new int [n+1];
    			 cnt=new int [n+1];
    			
    			for(int i=n-1;i>=0;i--) {
    			
    				int bn=i/block;
    				int l=(bn)*block;
    				int r=(bn+1)*block;
    				update(l,r,i);
  
    			}
    			for(int i=0;i<q;i++) {
    				int ans=0;
    				int in=sc.nextInt();
    				if(in==0) {
    					int a=sc.nextInt();
    					int b=sc.nextInt();
    					a--;
    					ar[a]=b;
    					int bn=a/block;
    					int l=bn*block;
    					int r=(bn+1)*block;
    					update(l,r,a);
    				}
    				else {
    					
    					int a=sc.nextInt();
    					a--;
    					int j=a;
    					int pre=j;
    					while(j<n) {
    						ans+=cnt[j];
    						pre=j;
    						j=next[j];
    					}
    					int cu=pre;
    					while(cu<n) {
    						pre=cu;
    						cu+=ar[cu];
    					}
    					out.append((pre+1)+" "+ans +"\n");
    				}
    			}
    		
    		}
    		System.out.println(out);
     
    	}
     
    	static long solve(long x, long y, long z) {
    		return (long) ((x - y) * (x - y) + (y - z) * (y - z) + (z - x) * (z - x));
    	}

	

		
	
	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

}