http://codeforces.com/problemset/problem/551/E

Professor GukiZ was playing with arrays again and accidentally discovered new function, which he called GukiZiana. For given array a, indexed with integers from 1to 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

将n平均分成sqrt(n)块，对每一块从小到大排序，并设置一个整体偏移量。 
修改操作：l~r区间内，对两端的块进行暴力处理，对中间的整体的块用整体偏移量标记增加了多少。时间复杂度： O(2*sqrt(n)+n/sqrt(n)). 
查询操作：对每一块二分，查找y-整体偏移量。找到最左边的和最右边的。时间复杂度：O(sqrt(n)*log(sqrt(n)))。 
代码如下：
 

#include <iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include <stdio.h>
using namespace std;
const int N=500000+100;
typedef long long  ll;
int n ,num,q ,op,sq,bl[N];
ll tag[N];
struct node{
    int id;
    ll x;
    node(){};
    bool operator <(const node& S)const{
        if(x==S.x) return id<S.id;
        return x<S.x;
    }
}a[N];

void updata(int l ,int r,ll x){
    for(int i=(bl[l]-1)*sq+1;i<=bl[l]*sq;i++){
        if(a[i].id>=l&&a[i].id<=r)
            a[i].x+=x;
    }
    sort(a+(bl[l]-1)*sq+1,a+min(bl[l]*sq,n)+1);
    for(int i=bl[l]+1;i<=bl[r]-1;i++)
        tag[i]+=x;
    if(bl[l]!=bl[r]){
        for(int i=(bl[r]-1)*sq+1;i<=min(bl[r]*sq,n);i++){
            if(a[i].id>=l&&a[i].id<=r)
                a[i].x+=x;
        }
        sort(a+(bl[r]-1)*sq+1,a+min(bl[r]*sq,n)+1);
    }
}
int BS1(int low, int high, ll x)
{
        int mid, ans=-1;
        while(low<=high){
                mid=(low+high)>>1;
                if(a[mid].x<=x){
                        ans=mid;
                        low=mid+1;
                }
                else high=mid-1;
        }
        return ans;
}
int BS2(int low, int high, ll x)
{
        int mid, ans=-1;
        while(low<=high){
                mid=(low+high)>>1;
                if(a[mid].x>=x){
                        ans=mid;
                        high=mid-1;
                }
                else low=mid+1;
        }
        return ans;
}

ll query(ll y){
    int maxl=0,minl=1,tmp;
    for(int i=1;i<=num;i++){
            tmp=BS2((i-1)*sq+1,min(i*sq,n),y-tag[i]);
            if(tmp!=-1&&a[tmp].x==y-tag[i]){
                    minl=a[tmp].id;//printf("%d\n",minl);
                    break;
            }
    }
    for(int i=num;i>0;i--){
            tmp=BS1((i-1)*sq+1,min(i*sq,n),y-tag[i]);
            if(tmp!=-1&&a[tmp].x==y-tag[i]){
                    maxl=a[tmp].id;//printf("%d\n",maxl);
                    break;
            }
    }
    return maxl-minl;
}

int main()
{

    scanf("%d%d",&n,&q);
    sq=(int)sqrt(n);
    num=n/sq;
    if(n%sq)num++;

    for(int i=1;i<=n;i++){
        bl[i]=(i-1)/sq+1;
        scanf("%I64d",&a[i].x);
        a[i].id=i;
    }
    for(int i=1;i<=num;i++){
        tag[i]=0;

        sort(a+(i-1)*sq+1,a+min(i*sq,n)+1);
    }
    int l ,r;
    ll x,y;
    for(int i=1;i<=q;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%I64d",&l,&r,&x);
            updata(l,r,x);
        }else{
            scanf("%I64d",&y);
            printf("%I64d\n",query(y));
        }
    }
    //cout << "Hello world!" << endl;
    return 0;
}