問題

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

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

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

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

 

制約

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

入力

N M QN M Q\\ AA\\ C1 C2 CNC_1 C_2 \dots C_N\\ query1query_1\\ query2query_2\\ \vdots\\ queryQquery_Q\\

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

XX

 

出力

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

 

サンプル

入力例
8 4 3
11
8 6 2 4 5 7 10 5
10
21
17

  

出力
4
6
5

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

提出


Go (1.21)