Problem: Professor GukiZ was playing with arrays again and accidentally discovered new function, which he called GukiZiana. For given array a, indexed with integers from 1 to n, and number y, GukiZiana(a, y) represents maximum value of j - i, such that aj = ai = y. If there is no y as an element in a, then GukiZiana(a, y) is equal to  - 1. GukiZ also prepared a problem for you. This time, you have two types of queries: 

  1. First type has form 1 l r x and asks you to increase values of all ai such that l ≤ i ≤ r by the non-negative integer x. 
  2. Second type has form 2 y and asks you to find value of GukiZiana(a, y). 



For each query of type 2, print the answer and make GukiZ happy!

Input

The first line contains two integers n, q (1 ≤ n ≤ 5 * 105, 1 ≤ q ≤ 5 * 104), size of array a, and the number of queries. 

The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 109), forming an array a. 

Each of next q lines contain either four or two numbers, as described in statement:

If line starts with 1, then the query looks like 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109), first type query.

If line starts with 2, then th query looks like 2 y (1 ≤ y ≤ 109), second type query.

Output

For each query of type 2, print the value of GukiZiana(a, y), for y value for that query.

Examples

Input

4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3


Output

2


Input

2 3
1 2
1 2 2 1
2 3
2 4


Output

0
-1

Solution (in JAVA):

Solution:
//package round307;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class E {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), Q = ni();
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		int s = (int)(Math.sqrt(Q)*3);
		int[][] qs = new int[Q][];
		for(int i = 0;i < Q;i++){
			int t = ni();
			if(t == 1){
				qs[i] = new int[]{1, ni()-1, ni()-1, ni()};
			}else{
				qs[i] = new int[]{2, ni()};
			}
		}
		
		int[] xs = new int[2*s+2];
		long[] atemp = new long[n];
		long[] plus = new long[n];
		for(int i = 0;i < Q;i += s){
			int j = Math.min(Q, i+s);
			int p = 0;
			for(int k = i;k < j;k++){
				if(qs[k][0] == 1){
					xs[p++] = qs[k][1];
					xs[p++] = qs[k][2]+1;
				}
			}
			xs[p++] = 0;
			xs[p++] = n;
			Arrays.sort(xs, 0, p);
			int pp = 0;
			for(int k = 0;k < p;k++){
				if(k == 0 || xs[k] != xs[k-1]){
					xs[pp++] = xs[k];
				}
			}
			p = -1;
			for(int k = 0;k < n;k++){
				atemp[k] = a[k]<<20|k;
			}
			for(int k = 0;k < pp-1;k++){
				Arrays.sort(atemp, xs[k], xs[k+1]);
			}
			Arrays.fill(plus, 0L);
			for(int k = i;k < j;k++){
				int[] q = qs[k];
				if(q[0] == 1){
					int from = Arrays.binarySearch(xs, 0, pp, q[1]);
					int to = Arrays.binarySearch(xs, 0, pp, q[2]+1);
					for(int z = from;z < to;z++){
						plus[z] += q[3];
					}
				}else{
					int inf = 9999999;
					int sup = -1;
					for(int z = 0;z < pp-1;z++){
						if(q[1]-plus[z] < 0)continue;
						// inf
						{
							int ind = Arrays.binarySearch(atemp, xs[z], xs[z+1], (q[1]-plus[z]<<20)-1);
							ind = -ind-1;
							if(ind < xs[z+1]){
								if((atemp[ind]>>>20) == q[1]-plus[z]){
									inf = Math.min(inf, (int)(atemp[ind]&(1<<20)-1));
								}
							}
						}
						// sup
						{
							int ind = Arrays.binarySearch(atemp, xs[z], xs[z+1], (q[1]-plus[z]+1L<<20)-1);
							ind = -ind-2;
							if(ind >= xs[z]){
								if((atemp[ind]>>>20) == q[1]-plus[z]){
									sup = Math.max(sup, (int)(atemp[ind]&(1<<20)-1));
								}
							}
						}
					}
					out.println(sup == -1 ? -1 : sup-inf);
				}
			}
			
			for(int k = 0;k < pp-1;k++){
				for(int l = xs[k];l < xs[k+1];l++){
					a[l] += plus[k];
					if(a[l] >= 1000000007)a[l] = 1000000007;
				}
			}
		}
	}
	
	void run() throws Exception
	{
		is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new E().run(); }
	
	private byte[] inbuf = new byte[1024];
	private int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}