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.*;

public class P22C {

  private static void solve() {
    int n = nextInt();
    int m = nextInt();

    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
      int v = nextInt();
      map.computeIfAbsent(v, (k) -> new ArrayList<>()).add(i + 1);
    }

    for (int i = 0; i < m; i++) {
      int l = nextInt();
      int r = nextInt();
      int x = nextInt();

      List<Integer> list = map.get(x);
      if (list == null) {
        out.println(l);
      } else {
        int lp = Collections.binarySearch(list, l);
        if (lp < 0) {
          out.println(l);
        } else {
          int rp = Collections.binarySearch(list, r);
          if (rp < 0) {
            out.println(r);
          } else {
            if (rp - lp == r - l) {
              out.println(-1);
            } else {
              out.println(bs(list, lp, rp));
            }
          }
        }

      }
    }
  }

  private static int bs(List<Integer> list, int lp, int rp) {
    int ilp = lp;
    int irp = rp;
    while (lp <= rp) {
      int mid = (lp + rp) >>> 1;

      if (mid - 1 >= ilp && list.get(mid) - list.get(mid - 1) > 1) {
        return list.get(mid) - 1;
      }

      if (mid + 1 <= irp && list.get(mid + 1) - list.get(mid) > 1) {
        return list.get(mid) + 1;
      }

      if (list.get(rp) - list.get(mid) != rp - mid) {
        lp = mid + 1;
      } else {
        rp = mid - 1;
      }
    }
    return -1;
  }


  private static void run() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);

    solve();

    out.close();
  }

  private static StringTokenizer st;
  private static BufferedReader br;
  private static PrintWriter out;

  private static String next() {
    while (st == null || !st.hasMoreElements()) {
      String s;
      try {
        s = br.readLine();
      } catch (IOException e) {
        return null;
      }
      st = new StringTokenizer(s);
    }
    return st.nextToken();
  }

  private static int nextInt() {
    return Integer.parseInt(next());
  }

  private static long nextLong() {
    return Long.parseLong(next());
  }

  public static void main(String[] args) {
    run();
  }
}