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:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
    static PrintWriter writer;

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

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

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

    static boolean eof = false;

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

    public static void main(String[] args) throws IOException {
        tokenizer = null;
        // reader = new BufferedReader(new FileReader("war.in"));
        // writer = new PrintWriter(new FileWriter("war.out"));
        reader = new BufferedReader(new InputStreamReader(System.in, "ISO-8859-1"));
        writer = new PrintWriter(System.out);
        banana();
        reader.close();
        writer.close();
    }

    static boolean test(long t, long a[], long m) {
        long min = 0;
        for (int i = 0; i < a.length; ++i) {
            if (a[i] == 0)
                continue;

            long cur = a[i];

        }

        return min <= m;
    }

    static void old() throws IOException {
        int n = nextInt();
        long m = nextInt();

        long a[] = new long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = nextInt();
        }

        long l = 0;
        long r = 1_000_000_000_000_000_000l;

        while (r - l > 1) {
            long t = (r + l) / 2;
            boolean ok = test(t, a, m);

            if (ok)
                r = t;
            else
                l = t;
        }

        System.out.println(r);
    }

    static int index(int x, int size) {
        if (x % size == 0)
            return x / size - 1;
        return x / size;
    }

    static void banana() throws IOException {
        int n = nextInt();
        int q = nextInt();

        int size = Math.min(n, 300);

        int count = n / size;
        if (n % size != 0)
            count++;

        long a[] = new long[count * size + 1];
        for (int i = 1; i <= n; ++i)
            a[i] = nextInt();

        long toAdd[] = new long[count];
        List<HashMap<Long, Integer>> mapki = new ArrayList<HashMap<Long, Integer>>();

        for (int i = 0; i < count; ++i) {
            for (int j = 1; j <= size; ++j) {
                int index = i * size + j;
                mapki.add(new HashMap<Long, Integer>());
                HashMap<Long, Integer> curMapka = mapki.get(i);

                if (curMapka.containsKey(a[index]))
                    curMapka.put(a[index], curMapka.get(a[index]) + 1);
                else
                    curMapka.put(a[index], 1);
            }
        }

        for (int qq = 0; qq < q; ++qq) {
            int query = nextInt();
            if (query == 1) {

                // maintaining.
                int l = nextInt();
                int r = nextInt();
                long x = nextInt();

                int li = index(l, size);
                int ri = index(r, size);

                for (int i = li + 1; i <= ri - 1; ++i) {
                    toAdd[i] += x;
                }

                if (li < ri) {
                    HashMap<Long, Integer> curMapka = mapki.get(li);
                    for (int i = l; i <= (li + 1) * size; ++i) {

                        if (curMapka.get(a[i]) > 1)
                            curMapka.put(a[i], curMapka.get(a[i]) - 1);
                        else
                            curMapka.remove(a[i]);

                        if (curMapka.containsKey(a[i] + x))
                            curMapka.put(a[i] + x, curMapka.get(a[i] + x) + 1);
                        else
                            curMapka.put(a[i] + x, 1);
                        a[i] += x;
                    }

                    curMapka = mapki.get(ri);
                    for (int i = ri * size + 1; i <= r; ++i) {

                        if (curMapka.get(a[i]) > 1)
                            curMapka.put(a[i], curMapka.get(a[i]) - 1);
                        else
                            curMapka.remove(a[i]);

                        if (curMapka.containsKey(a[i] + x))
                            curMapka.put(a[i] + x, curMapka.get(a[i] + x) + 1);
                        else
                            curMapka.put(a[i] + x, 1);
                        a[i] += x;
                    }
                } else {
                    HashMap<Long, Integer> curMapka = mapki.get(ri);
                    for (int i = l; i <= r; ++i) {
                        if (curMapka.get(a[i]) > 1)
                            curMapka.put(a[i], curMapka.get(a[i]) - 1);
                        else
                            curMapka.remove(a[i]);

                        if (curMapka.containsKey(a[i] + x))
                            curMapka.put(a[i] + x, curMapka.get(a[i] + x) + 1);
                        else
                            curMapka.put(a[i] + x, 1);
                        a[i] += x;
                    }
                }

            } else {
                long y = nextLong();
                int left = 0;
                int right = 0;
                boolean found = false;

                // left.
                for (int i = 0; i < count; ++i) {
                    if (mapki.get(i).containsKey(y - toAdd[i])) {
                        found = true;
                        for (int j = 1 + i * size; j <= (i + 1) * size; ++j)
                            if (a[j] == y - toAdd[i]) {
                                left = j;
                                break;
                            }

                        break;
                    }
                }
                if (!found) {
                    writer.println(-1);
                    continue;
                }
                // right.

                for (int i = count - 1; i >= 0; --i) {
                    if (mapki.get(i).containsKey(y - toAdd[i])) {
                        for (int j = (i + 1) * size; j >= 1 + i * size; --j)
                            if (a[j] == y - toAdd[i]) {
                                right = j;
                                break;
                            }

                        break;
                    }
                }
                writer.println(right - left);
            }
        }
    }
}