Ebihurai Search

問題

エビフライ専門店「Kotonoha」では、全部で $N$ 個のエビフライが販売されています。
それぞれのエビフライには値段があり、$i$ 番目のエビフライを買うためには $C_i$ 円が必要です。

また、$M$ 個以上買ったら $A$ 円割引されるクーポンを $10^{10^{100}}$ 枚持っています。
クーポンの使用は各クエリごとに1回のみです。

次の形式のクエリ $Q$ 個が与えられるため、各クエリを順番に処理してください。

• 1つのクエリごとに整数 $X$ が与えられます。$X$ 円で、最大で何個のエビフライを購入できるかを求めてください。

制約

• $1 \leq N, Q \leq 10^6\\$
• $1 \leq C_i \leq 10^9$
• $1 \leq M \leq N$
• $1 \leq A \leq 10^6$
• $1 \leq X \leq 10^{12}\\$
• 入力される数値は全て整数 　

入力

各クエリは以下の形式で表される。

出力

$Q$ 行出力せよ。
$i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。

サンプル

8 4 3
11
8 6 2 4 5 7 10 5
10
21
17

4
6
5

クーポンを使用することで $2, 3, 4, 8$ 番目の商品を買うことができます。