Problem: 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

2
6
-1
4

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import static java.lang.Math.E;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.*;


public class main{

 
    

    public static void main(String[] args) throws Exception{
    BufferedReader bf = new BufferedReader(new  InputStreamReader(System.in)) ;
    StringTokenizer st = new StringTokenizer(bf.readLine()) ;
    int aa = Integer.parseInt(st.nextToken()) ;
    seg a = new seg(aa) ;
    int b =Integer.parseInt(st.nextToken()) ;
     int in [] = new int [aa] ; 
     st = new StringTokenizer(bf.readLine()) ;
    for(int i = 0 ; i < aa ; i++)
      in [i] = Integer.parseInt(st.nextToken()) ;
    a.seg2(in, 0, aa-1, 0);
    
        
    StringBuilder sr = new StringBuilder() ;
   while(b-- != 0){
       st = new StringTokenizer(bf.readLine()) ;
       int i = Integer.parseInt(st.nextToken()) -1;
       int j = Integer.parseInt(st.nextToken()) -1;
       int x = Integer.parseInt(st.nextToken()) ;
       a.y = -1 ; a.z = -1 ;
       nd min = a.get(0, i , j, 0, aa-1);
       nd max = a.get2(0, i , j, 0, aa -1);
      
        if(x == min.a && x == max.a)
            sr.append("-1"+"\n");
        else
            if(x != max.a)
                sr.append(max.b + 1 +"\n");
            else if(x != min.a )
                sr.append(min.b + 1 +"\n");
   
   }
        System.out.print(sr);
    }}
class nd {
int a , b ;

    public nd(int x , int y) {
    a = x ;
    b = y ;
    }

}
class seg{

  nd ar [] ;
  nd ar2 [] ;

  int y = -1 , z = -1 ;

    public seg(int n ) {
        int i = 1 ;
        while(i < n )
        {
        i *=2 ;
        
        }
     ar = new nd [2 * i  -1] ;
     ar2 = new nd [2 * i  -1] ;
     
    }
  
    public  void seg2(int in[] , int l , int r , int p  ) {
    if(l == r)
    {ar[p] = new nd(in[l] ,l) ;  ar2[p] = new nd(in[l] ,l) ;}
    else
    {
    
    seg2(in ,l  , (l + r)/2 , p * 2+1) ;
    seg2(in ,(l + r)/2 + 1  ,r  , p * 2 + 2 ) ;
    
    if(ar[p * 2 + 1].a < ar[p*2+2].a)
    {
    ar[p] = new nd(ar[p * 2 + 1].a, ar[p * 2 + 1].b) ;
        
    }
    else
    {
    ar[p] = new nd(ar[p * 2 + 2].a, ar[p * 2 + 2].b) ;
       
    }
    
       if(ar2[p * 2 + 1].a > ar2[p * 2 + 2].a)
    {
    ar2[p] = new nd(ar2[p * 2 + 1].a, ar2[p * 2 + 1].b) ;
    
    }
    else
    {
    ar2[p] = new nd(ar2[p * 2 + 2].a, ar2[p * 2 + 2].b) ;
    
    }
    }
    }
    public nd get(int p , int i , int j , int l , int r ) {
     if(i <= l && j >= r)
       { return ar[p] ;}
       if(i > r || j < l )
           return new nd(Integer.MAX_VALUE, -1) ;
       int mid = (l + r) / 2 ;
       nd p1 = get(2 * p + 1 , i, j, l, mid) ;
       nd p2 = get(2 * p + 2 , i, j, mid + 1, r) ;
       if(p1.a < p2.a )
       {
       
       return p1 ;
       
       }
       else 
       {
       
       
       return p2 ;
       }  
    } 
    
   

 public nd get2(int p , int i , int j , int l , int r ) {
       if(i <= l && j >= r)
       { return ar2[p] ;}
       if(i > r || j < l )
           return new nd(Integer.MIN_VALUE, -1) ;
       int mid = (l + r) / 2 ;
       nd p1 = get2(2 * p + 1 , i, j, l, mid) ;
       nd p2 = get2(2 * p + 2 , i, j, mid + 1, r) ;
       if(p1.a > p2.a )
       {
       
       return p1 ;
       
       }
       else 
       {
       
       
       return p2 ;
       }  
    }



}