Modular Query

Time Limit : 3 sec, Memory Limit : 65536 KB

モジュロ・クエリ

あなたに N 枚のカードを渡します。どのカードにも一つだけ自然数が書いてあります。ただし、同じ数が書いてあることはありません。

これから質問として、適当な自然数を言います。あなたが持っているカードに書いてある数を私が言った数で割ったときに得られる余りのうち最も大きなものを答えてください。

たとえば、あなたは 3 枚のカードを持っていて、それぞれ 9、3、8 と書いてあるとします。私が「4」と言ったら、9 と 3 と 8 をそれぞれ4 で割った余りを求めてください。余りはそれぞれ 1、3、0 ですが、この中でもっとも大きな余りは3 なので、3 が正しい答えになります。

では始めましょうか。え? カードがいっぱいあるとたいへんだ? しょうがないですね。それではコ ンピュータを使って最大の余りを見つけることにしましょう。カードに書いてある数を、質問された数で割った余りのうち、最大のものを見つけるプログラムを作成してください。なお、質問は1回だけでなく何度もしますが、同じ数を 2 回以上質問することはありません。

入力

入力は1つのデータセットからなる。入力データは以下の形式で与えられる。

N Q
c1 c2 ... cN
q1
q2
:
qQ

1行目にカードの枚数 N (2 ≤ N ≤ 300000) と質問の回数 Q (2 ≤ Q ≤ 100000) が1つの空白区切りで与えられ、2行目にカードに書かれた数 ci (1 ≤ ci ≤ 300000) が1つの空白区切りで与えられる。続くQ 行に質問として与えられる数 qi (1 ≤ qi ≤ 300000) が与えられる。

出力

質問ごとに最大の余りを1行に出力する。

入力例

3 3
9 3 8
4
6
5

出力例

3
3
4

Source: PC Koshien 2012 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2012-11-10
http://www.pref.fukushima.jp/pc-concours/