問題文

長さ $N$ の数列 $A = (a_1, a_2, \\dots, a_N)$ があります。
以下で説明される $Q$ 個のクエリに答えてください。

• クエリ $i$ : 整数の組 $(x_i, k_i)$ が与えられます。$A$ の要素を $a_1, a_2, \\dots$ と前から順に見ていったときに、数 $x_i$ が $k_i$ 回目に登場するのは $A$ の前から何番目の要素を見たときかを出力してください。
  ただし条件を満たす要素が存在しない場合は $\-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$ $\\dots$ $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

$A$ の中で $1$ は $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