問題
長さ$ \ 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 \ $です。