1674 - Treasure Ticket

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer woody_1227 / x 7 / 統計 /

    タグ:

TLE
1sec
MLE
64MB
得点
100

問題

ある日、ゆたかくんは、宝くじを買うことにしました。
ゆたかくんが買いたいと思っている宝くじのくじ番号は、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なので、これを出力します。
ゆたかくんは、このくじ番号を選んでくじを買うことにします。