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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author K0T
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskE {

    static int blockLen;

    int n, q;
    int type;
    int le, ri, x;
    int blocksCount;
    int[] a;
    int[] sz;
    long[] add;
    int[] ptr;
    boolean[] was;
    Pair[] toFind;
    Pair[][] sorted;
    Pair[][] blocks;

    public void solve(int testNumber, InputReader scn, PrintWriter pw) {
        n = scn.nextInt();
        q = scn.nextInt();
        a = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            a[i] = scn.nextInt();
        }
        blockLen = 1111;
        toFind = new Pair[blockLen + 10];
        sz = new int[n / blockLen + 3];
        for (int i = 1; i <= n; i++) {
            sz[(i - 1) / blockLen + 1]++;
        }
        blocksCount = (n - 1) / blockLen + 1;
        was = new boolean[blocksCount + 2];
        blocks = new Pair[blocksCount + 2][];
        sorted = new Pair[blocksCount + 2][];
        for (int i = 1; i <= blocksCount; i++) {
            blocks[i] = new Pair[sz[i] + 2];
            sorted[i] = new Pair[sz[i] + 2];
        }
        Arrays.fill(was, false);
        ptr = new int[blocksCount + 2];
        Arrays.fill(ptr, 0);
        for (int i = 1; i <= n; i++) {
            blocks[(i - 1) / blockLen + 1][++ptr[(i - 1) / blockLen + 1]] = new Pair(a[i], i);
        }
        StringBuilder stringBuilder = new StringBuilder();
        add = new long[blocksCount + 2];
        for (int queries = 0; queries < q; queries++) {
            type = scn.nextInt();
            if (type == 1) {
                le = scn.nextInt();
                ri = scn.nextInt();
                x = scn.nextInt();
                modifyDecomposition(le, ri, x);
            } else {
                x = scn.nextInt();
                pw.println(findAns(x));
            }
        }
    }

    private int findAns(int x) {
        int begin, end;
        begin = 2 * 1000 * 1000 * 1000;
        end = -2 * 1000 * 1000 * 1000;
        int le, ri;
        for (int i = 1; i <= blocksCount; i++) {
            if (was[i] == false) {
                was[i] = true;
                for (int j = 1; j <= sz[i]; j++) {
                    sorted[i][j] = blocks[i][j];
                }
                Arrays.sort(sorted[i], 1, sz[i] + 1);
            }
            le = 1;
            ri = sz[i] + 1;
            while (ri - le > 1) {
                int mid = (le + ri) >> 1;
                if (sorted[i][mid].val + add[i] <= 1L * x) {
                    le = mid;
                } else {
                    ri = mid;
                }
            }
            if (sorted[i][le].val + add[i] == 1L * x) {
                begin = Math.min(begin, sorted[i][le].pos);
                end = Math.max(end, sorted[i][le].pos);
            }
            le = 1;
            ri = sz[i] + 1;
            while (ri - le > 1) {
                int mid = (le + ri) >> 1;
                if (sorted[i][mid].val + add[i] < 1L * x) {
                    le = mid;
                } else {
                    ri = mid;
                }
            }
            if (sorted[i][le].val + add[i] == 1L * x) {
                le += 0;
            } else if (le + 1 <= sz[i] && sorted[i][le + 1].val + add[i] == 1L * x) {
                ++le;
            } else le = -2;
            if (le > 0) {
                begin = Math.min(begin, sorted[i][le].pos);
                end = Math.max(end, sorted[i][le].pos);
            }
        }
        if (begin + end == 0) {
            return -1;
        } else {
            return end - begin;
        }
    }

    private void modifyDecomposition(int le, int ri, int x) {
        for (int i = le; i <= ri; ) {
            if ((i - 1) % blockLen == 0 && i + sz[(i - 1) / blockLen + 1] - 1 <= ri) {
                add[(i - 1) / blockLen + 1] += (1L * x);
                i += sz[(i - 1) / blockLen + 1];
            } else {
                int posInBlock = i % blockLen;
                if (posInBlock == 0) {
                    posInBlock = sz[(i - 1) / blockLen + 1];
                }
                blocks[(i - 1) / blockLen + 1][posInBlock].val += (1L * x);
                was[(i - 1) / blockLen + 1] = false;
                ++i;
            }
        }
    }
}

class Pair implements Comparable {

    long val;
    int pos;

    Pair(long val, int pos) {
        this.val = val;
        this.pos = pos;
    }

    public int compareTo(Object o) {
        Pair pair = (Pair)o;
        if (this.val != pair.val) {
            if (this.val < pair.val) {
                return -1;
            } else {
                return 1;
            }
        }
        if (this.pos < pair.pos) {
            return -1;
        } else {
            return 1;
        }
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

}