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.util.*;
import java.io.*;
import java.math.BigInteger;
import java.text.*;
public class Main {
    static long mod = 1000_000_007;
    static long mod1 = 998244353;
    static boolean fileIO = true;
    static boolean memory = true;
    static FastScanner f;
    static PrintWriter pw;
    static double eps = (double)1e-6;
    static int oo = (int)1e7;
    static int segMin[] , segMax[];

    public static void build(int arr[] , int n) {
        segMin = new int[2 * n];
        segMax = new int[2 * n];

        //Assign value to leaves of segment tree
        for(int i = 0 ; i < n ; ++i) {
            segMin[n + i] = arr[i];
            segMax[n + i] = arr[i];
        } 
        
        //Assign value to internal node to compute minimum in a given range
        for(int i = n - 1; i >= 1; --i) {
            segMin[i] = Math.min(segMin[2 * i] , segMin[2 * i + 1]);
            segMax[i] = Math.max(segMax[2 * i] , segMax[2 * i + 1]); 
        }
    }

    public static int queryMin(int l , int r , int n) {
        if(l == r)
            return segMin[l + 1];
        //Change indices to leaf node
        l += n;
        r += n;
        int ans = oo;
        while(l < r) {
            if((l & 1) == 1) ans = Math.min(ans , segMin[l++]);
            if((r & 1) == 1) ans = Math.min(ans , segMin[--r]);
            l /= 2;
            r /= 2;
        }
        return ans;
    }

    public static int queryMax(int l , int r , int n) {
        if(l == r)
            return segMax[l + 1];
        //Change indices to leaf node
        l += n;
        r += n;
        int ans = -oo;
        while(l < r) {
            if((l & 1) == 1) ans = Math.max(ans , segMax[l++]);
            if((r & 1) == 1) ans = Math.max(ans , segMax[--r]);
            l /= 2;
            r /= 2;
        }
        return ans;
    }

    public static void solve() throws Exception {
        int n = f.ni(); int q = f.ni();
        int arr[] = new int[n];
        HashMap<Integer , TreeSet<Integer>> mp = new HashMap<>();
        
        for (int i = 0; i < n; ++i) {
            arr[i] = f.ni();
            if (mp.get(arr[i]) == null) mp.put(arr[i] , new TreeSet<>());
            mp.get(arr[i]).add(i + 1);
        }

        build(arr , n);
        for (int i = 0; i < q; ++i) {
            int l = f.ni(); int r = f.ni(); int x = f.ni();
            int min = queryMin(l - 1 , r , n);
            int max = queryMax(l - 1 , r , n);

            if (min == max && max == x) {
                pn(-1);
                continue;
            }

            if (min != x) {
                if (mp.get(min).contains(l)) pn(l);
                else if (mp.get(min).contains(r)) pn(r);
                else if (mp.get(min).lower(r) != null) pn(mp.get(min).lower(r));
                else if (mp.get(min).higher(l) != null) pn(mp.get(min).higher(l));
            } 
            else {
                if (mp.get(max).contains(l)) pn(l);
                else if (mp.get(max).contains(r)) pn(r);
                else if (mp.get(max).lower(r) != null) pn(mp.get(max).lower(r));
                else if (mp.get(max).higher(l) != null) pn(mp.get(max).higher(l));  
            }
        }
    }
 
    public static void main(String[] args)throws Exception {
        if(memory) new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "", 1 << 28).start();
        else new Main().run();
    }
        
/******************************END OF MAIN PROGRAM*******************************************/
    void run()throws Exception {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            f = new FastScanner("");
            pw = new PrintWriter(System.out);
        }
        else {
            f = new FastScanner();
            pw = new PrintWriter(System.out);
            //fw = new FileWriter("!out.txt");
        }
        //pre();
        int t = 1;
        int tt = 1;
        while(t --> 0) {
            //fw.write("Case #" + (tt++) + ": ");
            //fw.write("\n");
            solve();
        }
        pw.flush(); 
        pw.close();
        //fw.close();  
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner(String str) throws Exception {
            try {
                br = new BufferedReader(new FileReader("!a.txt"));
            }
            catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public String next()throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        public int ni() throws IOException {return Integer.parseInt(next());}
 
        public long nl() throws IOException {return Long.parseLong(next());}
 
        public String nextLine() throws IOException {return br.readLine();}
 
        public double nd() throws IOException {return Double.parseDouble(next());}
 
    }
 
    public static void pn(Object... o) {for(int i = 0; i < o.length; ++i) pw.print(o[i] + (i + 1 < o.length ? " ": "\n"));}
    public static void p(Object... o) {for(int i = 0; i < o.length; ++i) pw.print(o[i] + (i + 1 < o.length ? " " : ""));}
    public static void pni(Object... o) {for(Object obj : o) pw.print(oo + " "); pw.println(); pw.flush();}
    public static int gcd(int a,int b){if(b==0)return a;else{return gcd(b,a%b);}}
    public static long gcd(long a,long b){if(b==0l)return a;else{return gcd(b,a%b);}}
    public static long lcm(long a,long b){return (a*b/gcd(a,b));}
    public static long pow(long a,long b){long res=1;while(b>0){if((b&1)==1)res=res*a;b>>=1;a=a*a;}return res;}
    public static int pow(int a,int b){int res=1;while(b>0){if((b&1)==1)res=res*a;b>>=1;a=a*a;}return res;}
    public static long mpow(long a,long b, long m){long res=1;while(b>0){if((b&1)==1)res=((res%m)*(a%m))%m;b>>=1;a=((a%m)*(a%m))%m;}return res;}
    public static long mul(long a , long b , long mod){return ((a%mod)*(b%mod)%mod);}
    public static long adp(long a , long b){return ((a%mod)+(b%mod)%mod);}
    public static int dig(long a){int cnt=0;while(a>0){a/=10;++cnt;}return Math.max(1,cnt);}
    public static int dig(int a){int cnt=0;while(a>0){a/=10;++cnt;}return Math.max(1,cnt);}
    public static boolean isPrime(long n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(long i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
    public static boolean isPrime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
    public static HashSet<Long> factors(long n){HashSet<Long> hs=new HashSet<Long>();for(long i=1;i<=(long)Math.sqrt(n);i++){if(n%i==0){hs.add(i);hs.add(n/i);}}return hs;}
    public static HashSet<Integer> factors(int n){HashSet<Integer> hs=new HashSet<Integer>();for(int i=1;i<=(int)Math.sqrt(n);i++){if(n%i==0){hs.add(i);hs.add(n/i);}}return hs;}
    public static HashSet<Long> pf(long n){HashSet<Long> ff=factors(n);HashSet<Long> ans=new HashSet<Long>();for(Long i:ff)if(isPrime(i))ans.add(i);return ans;}
    public static HashSet<Integer> pf(int n){HashSet<Integer> ff=factors(n);HashSet<Integer> ans=new HashSet<Integer>();for(Integer i:ff)if(isPrime(i))ans.add(i);return ans;}
    public static int gnv(char c){return Character.getNumericValue(c);}
    public static void sort(int[] a){ArrayList<Integer> l=new ArrayList<>();for(int i:a)l.add(i);Collections.sort(l);for(int i=0;i<a.length;++i)a[i]=l.get(i);}
    public static void sort(long[] a){ArrayList<Long> l=new ArrayList<>();for(long i:a)l.add(i);Collections.sort(l);for(int i=0;i<a.length;++i)a[i]=l.get(i);}
    public static void sort(ArrayList<Integer> a){Collections.sort(a);}
}