给定数组 a,其中包含 n 个整数和 m 个查询。第 i 个查询由三个整数 li、ri、xi 给出。
对于第 i 个查询,找到任意位置 pi (li ≤ pi ≤ ri),使得 api ≠ xi。
输入
第一行包含两个整数 n, m (1 ≤ n, m ≤ 2·105) — a 中的元素数量和查询次数。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 数组 a 的元素。
接下来的 m 行每行包含三个整数 li、ri、xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — 第 i 个查询的参数。
输出
打印 m 行。在第 i 行打印整数 pi — 段 [li, ri] 中任何不等于 xi 的数字的位置,如果没有这样的数字,则值 - 1。
示例
输入 #1
6 4 1 2 1 1 3 5 1 4 1 2 6 2 3 4 1 3 4 2
输出 #1
2 6 -1 4