問題文

NN 個の木の実があります。
i(1iN)i \: (1 ≦ i ≦ N) 個目の木の実は、AiA_i グラムの重さがあり、食べると攻撃力が 11 だけ上昇します。

また、MM 体のモンスターがいます。
i(1iM)i \: (1 ≦ i ≦ M) 体目のモンスターは、木の実を食べる前の攻撃力は 00 で、木の実を BiB_i グラムまで食べることができます。

それぞれのモンスターについて、木の実をあげた時に得られる攻撃力の最大値を求めてください。

制約

  • 1N,M1051 \leq N, M \leq 10^{5}
  • 1Ai109(1iN)1 \leq A_i \leq 10^{9} \: (1 \leq i \leq N)
  • 1Bi109(1iM)1 \leq B_i \leq 10^{9} \: (1 \leq i \leq M)
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
A1 A2 …… AN
B1 B2 …… BM

出力

問題の答えを一行に出力せよ。

入出力例

入力例1
5 3
2 5 1 3 6
2 10 17
出力例1
1 3 5
  • 11 体目のモンスターは、重さが 22 の木の実を食べることによって攻撃力を 11 にすることができます。
  • 22 体目のモンスターは、重さが 2,5,12, 5, 1 の木の実を食べることによって攻撃力を 33 にすることができます。
  • 33 体目のモンスターは、全ての木の実を食べることができるので、攻撃力を 55 にすることができます。
入力例2
10 6
74 36 84 97 28 40 38 29 64 65 
736 351 837 970 273 395 
出力例2
10 7 10 10 6 8 

Submit


Go (1.21)