codeforces 622C Not Equal on a Segment

You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi.

For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the number of elements in a and the number of queries.

The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.

Each of the next m lines contains three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — the parameters of the i-th query.

Output

Print m lines. On the i-th line print integer pi — the position of any number not equal to xi in segment [li, ri] or the value - 1 if there is no such number.

Examples

input

6 4
1 2 1 1 3 5
1 4 1
2 6 2
3 4 1
3 4 2

output

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<map>
  4 #include<stack>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 typedef long long ll;
  9 const int maxn=2e5+5;
 10 const int INF=0x3f3f3f3f;
 11 int pos=0;
 12 struct tree
 13 {
 14     int l,r,minval,maxval,minval_id,maxval_id;
 15 }s[maxn<<2];
 16 int check1(int a,int b)
 17 {
 18     if(s[a].minval>s[b].minval)
 19         a=b;
 20     return a;
 21 }
 22 int check2(int a,int b)
 23 {
 24     if(s[a].maxval<s[b].maxval)
 25         a=b;
 26     return a;
 27 }
 28 void pushup(int rt)
 29 {
 30     if(s[rt].minval>s[rt<<1].minval)s[rt].minval=s[rt<<1].minval,s[rt].minval_id=s[rt<<1].minval_id;
 31     if(s[rt].minval>s[rt<<1|1].minval)s[rt].minval=s[rt<<1|1].minval,s[rt].minval_id=s[rt<<1|1].minval_id;
 32     if(s[rt].maxval<s[rt<<1].maxval)s[rt].maxval=s[rt<<1].maxval,s[rt].maxval_id=s[rt<<1].maxval_id;
 33     if(s[rt].maxval<s[rt<<1|1].maxval)s[rt].maxval=s[rt<<1|1].maxval,s[rt].maxval_id=s[rt<<1|1].maxval_id;
 34 }
 35 void build(int l,int r,int rt)
 36 {
 37     s[rt].minval=INF,s[rt].maxval=-INF;
 38     s[rt].l=l,s[rt].r=r;
 39     if(l==r)
 40     {
 41         int t;
 42         scanf("%d",&t);
 43         s[rt].maxval=s[rt].minval=t;
 44         pos++;
 45         s[rt].minval_id=pos;
 46         s[rt].maxval_id=pos;
 47         return;
 48     }
 49     int m=(l+r)>>1;
 50     build(l,m,rt<<1);
 51     build(m+1,r,rt<<1|1);
 52     pushup(rt);
 53 }
 54 int query1(int l,int r,int rt)
 55 {
 56     if(l==s[rt].l&&r==s[rt].r)
 57         return rt;
 58     int m=(s[rt].l+s[rt].r)>>1;
 59     if(l>m)
 60         return query1(l,r,rt<<1|1);
 61     else if(r<=m)
 62         return query1(l,r,rt<<1);
 63     else
 64     {
 65         int t1=query1(l,m,rt<<1),t2=query1(m+1,r,rt<<1|1);
 66         return check1(t1,t2);
 67     }
 68 }
 69 int query2(int l,int r,int rt)
 70 {
 71     if(l==s[rt].l&&r==s[rt].r)
 72         return rt;
 73     int m=(s[rt].l+s[rt].r)>>1;
 74     if(l>m)
 75         return query2(l,r,rt<<1|1);
 76     else if(r<=m)
 77         return query2(l,r,rt<<1);
 78     else
 79     {
 80         int t1=query2(l,m,rt<<1),t2=query2(m+1,r,rt<<1|1);
 81         return check2(t1,t2);
 82     }
 83 }
 84 int main()
 85 {
 86     int n,m;
 87     scanf("%d%d",&n,&m);
 88     build(1,n,1);
 89     while(m--)
 90     {
 91         int l,r,x;
 92         scanf("%d%d%d",&l,&r,&x);
 93         int rt1=query1(l,r,1);
 94         int rt2=query2(l,r,1);
 95         bool key=0;
 96         int ans;
 97         if(s[rt1].minval!=x)
 98             ans=s[rt1].minval_id,key=1;
 99         if(s[rt2].maxval!=x)
100             ans=s[rt2].maxval_id,key=1;
101         key?printf("%d
",ans):puts("-1");
102     }
103     return 0;
104 }

codeforces 622C Not Equal on a Segment

C. Not Equal on a Segment