問題
ある日、ゆたかくんは、宝くじを買うことにしました。
ゆたかくんが買いたいと思っている宝くじのくじ番号は、N種類の数字$A_i$($1≦i≦N$)の中から重複ありで数字を選び、$M$桁並べた数字からなっています。
ゆたかくんは、これまでに当選したことがあるくじ番号を選べば、当選する可能性が高いのではないかと考えました。
いま手元に、「これまでに『あり得るくじ番号のうち、$X_j$($1≦j≦M$)番目に小さい番号』は当選したことがある」という情報が$Q$個あります。
しかし、このままでは、情報が分かりにくいので、それぞれの情報が指すくじ番号を求めることにしました。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $A_1$ $A_2$ .. $A_N$ $Q$ $X_1$ $X_2$ .. $X_Q$
出力
$Q$行にわたって、くじ番号を出力してください。
ただし、出力の末尾には改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 ≦ N ≦ 10$
- $1 ≦ M ≦ 20$
- $0 ≦ A_i ≦ 9$
- $A_i(1 ≦ i ≦ N)$は相異なる
- $1 ≦ Q ≦ 2 × 10^{5}$
- $1 ≦ X_i ≦ 10^{18}$
- $X_i$が指すくじ番号は存在する
- 入力はすべて整数である
入出力例
入力例1
3 4 1 2 7 1 15
出力例1
1227この宝くじの「あり得るくじ番号」の中で、
15番目に小さい番号は、1227なので、これを出力します。
ゆたかくんは、このくじ番号を選んでくじを買うことにします。