← 返回题目列表

Codeforces · 622/C

C. 段上不相等

中文机器翻译题面 查看原题

给定数组 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