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 block_size = 710;
const long long mod = 1e9 + 7;
const long double eps = 1e-9;
const int inf = mod;
const double PI = atan(1) * 4;
template <typename T>
inline int sign(const T& a) {
  if (a < 0) return -1;
  if (a > 0) return 1;
  return 0;
}
template <typename T>
inline void in(T& x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
long long delta[block_size];
vector<pair<long long, int>> sorted[block_size];
long long num[500010];
int n, q;
void build() {
  for (auto& i : sorted) {
    i.reserve(block_size);
  }
  for (long long i = 0; i < n; i++) {
    sorted[i / block_size].push_back({num[i], i});
  }
  for (auto& i : sorted) {
    sort(i.begin(), i.end());
  }
}
void query(long long y) {
  int a = inf, b = -1;
  for (long long i = 0; i < block_size; i++) {
    auto p = lower_bound(sorted[i].begin(), sorted[i].end(),
                         make_pair(y - delta[i], 0));
    if (p == sorted[i].end() || p->first != y - delta[i]) continue;
    if (a == inf) a = p->second;
    p = upper_bound(sorted[i].begin(), sorted[i].end(),
                    make_pair(y - delta[i], inf));
    --p;
    b = p->second;
  }
  if (a == inf) {
    puts("-1");
  } else {
    printf("%d\n", b - a);
  }
}
void rebuild(int id) {
  sorted[id].clear();
  for (int i = id * block_size; i < min(n, (id + 1) * block_size); i++) {
    sorted[id].push_back({num[i], i});
  }
  sort(sorted[id].begin(), sorted[id].end());
}
void change(long long l, long long r, long long x) {
  for (int i = l; i <= r;) {
    if (i % block_size == 0 && r >= (i + block_size - 1)) {
      delta[i / block_size] += x;
      i += block_size;
    } else {
      for (int j = i;
           j <= min(int(r), i / block_size * block_size + block_size - 1);
           j++) {
        num[j] += x;
      }
      rebuild(i / block_size);
      i = i / block_size * block_size + block_size;
    }
  }
}
int main() {
  cin >> n >> q;
  for (long long i = 0; i < n; i++) in(num[i]);
  build();
  for (long long i = 0; i < q; i++) {
    int t;
    in(t);
    if (t == 1) {
      int l, r;
      long long x;
      in(l);
      in(r);
      in(x);
      l--, r--;
      change(l, r, x);
    } else {
      int y;
      in(y);
      query(y);
    }
  }
  return 0;
}