003 - Find Kth

問題

長さ$ \ N \ $の数列$ \ A \ $が与えられます。これを$ \ M \ $個繋げた数列を$ \ B = (B_1,B_2,\ldots,B_{NM}) \ $とします。$Q \ $個のクエリに答えてください。$i \ $番目のクエリは以下の通りです。

• 数列$ \ B \ $のなかで$ \ k_i \ $番目に小さい値を出力せよ。

入力

入力は以下の形式で標準入力から与えられる。

$N \ M \ Q$
$A_1 \ A_2 \ \ldots \ A_N$
$k_1 \ k_2 \ \ldots \ k_Q$

出力

各クエリに対する答えを改行区切りで出力せよ。

制約

• $1 \leq N,M,Q \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• $1 \leq k_i \leq NM$
• 入力は全て整数

入出力例

入力例

3 2 3
1 2 3
5 1 6

出力例

3
1
3

数列$ \ A = (1, 2, 3) \ $を$ \ 2 \ $個繋げた数列$ \ B = (1, 2, 3, 1, 2, 3) \ $です。この中で$ \ 5,1,6 \ $番目に小さい値はそれぞれ$ \ 3, 1, 3 \ $です。