题目描述

我们有一个长度为 $N$ 的数列：$A = (a_1, a_2, \ldots, a_N)$。
处理下面的 $Q$ 个查询。

• 第 $i$ 个查询：给定一对整数 $(x_i, k_i)$。从开头逐个查看数列 $A$ 的元素：$a_1, a_2, \ldots$。第 $k_i$ 次出现的数 $x_i$ 是哪个元素？
  如果不存在这样的元素，则输出 $-1$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^9$ $(1 \leq i \leq N)$
• $0 \leq x_i \leq 10^9$ $(1 \leq i \leq Q)$
• $1 \leq k_i \leq N$ $(1 \leq i \leq Q)$
• 输入中的所有值都是整数。

输入

从标准输入读入数据，输入的格式如下：

$N$ $Q$ $a_1$ $a_2$ $\ldots$ $a_N$ $x_1$ $k_1$ $x_2$ $k_2$ $\vdots$ $x_Q$ $k_Q$

输出

打印 $Q$ 行。第 $i$ 行应该包含查询 $i$ 的答案。

示例输入 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

示例输出 1

1
2
5
-1
3
6
-1
-1

数 $1$ 在数列 $A$ 中出现在 $a_1, a_2, a_5$。因此，查询 $1$ 到 $4$ 的答案依次为 $1, 2, 5, -1$。

示例输入 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

示例输出 2

2
-1