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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500100;
const int root = 800;
long long lazy[root];
unordered_set<long long> s[root];
long long v[MAXN];
signed main() {
  memset(lazy, 0, sizeof lazy);
  long long n, m;
  scanf("%lld %lld", &n, &m);
  for (long long i = 0; i < n; i++)
    scanf("%lld", &v[i]), s[i / root].insert(v[i]);
  for (long long i = 1; i <= m; i++) {
    long long t;
    scanf("%lld", &t);
    if (t == 1) {
      long long l, r, x;
      scanf("%lld %lld %lld", &l, &r, &x);
      l -= 1, r -= 1;
      s[l / root].clear();
      for (long long j = (l / root) * root; j < min((l / root + 1) * root, n);
           j++) {
        if (j >= l && j <= r) v[j] += x;
        s[l / root].insert(v[j]);
      }
      if (l / root == r / root) continue;
      for (long long j = l / root + 1; j < r / root; j++) {
        lazy[j] += x;
      }
      s[r / root].clear();
      for (long long j = (r / root) * root; j < min((r / root + 1) * root, n);
           j++) {
        if (j <= r && j >= l) v[j] += x;
        s[r / root].insert(v[j]);
      }
    }
    if (t == 2) {
      long long y, ini, fim;
      scanf("%lld", &y);
      bool flag = false;
      for (long long j = 0; j < root; j++) {
        if (s[j].find(y - lazy[j]) != s[j].end()) {
          flag = true;
          for (long long k = j * root; k < (j + 1) * root; k++)
            if (v[k] == y - lazy[j]) {
              ini = k;
              break;
            }
          break;
        }
      }
      if (flag == false) {
        printf("-1\n");
        continue;
      }
      for (long long j = root - 1; j >= 0; j--) {
        if (s[j].find(y - lazy[j]) != s[j].end()) {
          flag = true;
          for (long long k = min((j + 1) * root - 1, n - 1); k >= j * root;
               k--) {
            if (v[k] == y - lazy[j]) {
              fim = k;
              break;
            }
          }
          break;
        }
      }
      printf("%lld\n", fim - ini);
    }
  }
}