D: 矢 / Arrow

問題

rodea 君は 1 次元座標系の中におり、x = 0 の場所に立っている。この位置から、x = N の位置にある的を目がけて、 常に速さ 1 で移動する正の整数の長さの矢を投げる。しかし、rodea 君は非力なため、 区間 0 \leq x \leq N の中に合計 M 個の送風機を置くことにしている。

ここで、矢の先端から根元までの位置に 1 つの送風機も含まれない場合を「損失」と定義する。損失の判定は、矢の先端が x = 1, 2, 3, $\ldots$, N に到達した際に行う（つまり、合計 N 回行う）。

このとき、以下のクエリを Q 回処理せよ。

• 「損失」許容可能な回数 l_i が与えられる。すなわち、N 回の判定において、「損失」が合計 l_i 回以下なら矢を的に届けることが可能である。このときの、矢を的に届けるために必要な最短の矢の長さを求める。

入力形式

N M
m_1 m_2 $\ldots$ m_M
Q
l_1 l_2 $\ldots$ l_Q

1 行目に距離 N と送風機の個数 M が空白区切りで与えられる。

2 行目に、M 個の送風機それぞれの位置が与えられる。m_i=j のとき、 i 番目の送風機は x=j-1 と x=j の丁度中間に位置している。

3 行目にクエリの個数 Q が与えられ、4 行目に「損失」許容可能な回数 l_i が Q 個与えられる。

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq N
• 1 \leq m_1 < m_2 < $\ldots$ < m_M \leq N
• 1 \leq Q \leq 10^5
• 0 \leq l_i \leq 10^5 (1 \leq i \leq Q)

出力形式

与えられる Q 個の l_i に対して考えられる最短の矢の長さを、順に改行して出力せよ。

ただし、条件を満たす正の整数の長さの矢が存在しない場合は -1 を出力するものとする。

入力例1

5 1
2
1
3

出力例1

2

矢の先端が x = 1 に到達したとき、先端から根元までに送風機は含まれないので、「損失」回数は 1 になる。

矢の先端が x = 2 に到達したとき、先端から根元までに送風機は含まれるので、「損失」回数は 1 のままである。

矢の先端が x = 3 に到達したとき、先端から根元までに送風機は含まれるので、「損失」回数は 1 のままである。

矢の先端が x = 4 に到達したとき、先端から根元までに送風機は含まれないので、「損失」回数は 2 になる。

矢の先端が x = 5 に到達したとき、先端から根元までに送風機は含まれないので、「損失」回数は 3 になる。

長さ 2 より短い矢を投げる場合、「損失」回数が 3 よりも多くなるため、長さ 2 の矢を投げるときが条件を満たす最短の矢の長さである。

入力例2

11 3
2 5 9
3
1 4 8

出力例2

4
3
1