問題文

高橋くんは AtCoder 商店を経営しています。 AtCoder 商店には $N$ 人の客が訪れ、$M$ 個の商品が売られています。 $i$ 番目 $(1\\leq i\\leq N)$ の客は購買意欲 $B _ i$ を持っています。 $j$ 番目 $(1\\leq j\\leq M)$ の商品の商品価値は $C _ j$ です。

高橋くんはそれぞれの商品に値段をつけます。 $i$ 番目の客は、$j$ 番目の商品の値段 $P _ j$ が次の条件を満たすような商品のみを、すべて $1$ 個ずつ購入します。

• $B _ i+C _ j\\geq P _ j$

$j=1,2,\\ldots,M$ について、高橋くんが売り上げが最大になるような値段をつけたときの $j$ 番目の商品の売り上げを求めてください。 ただし、$j$ 番目の商品の売り上げとは、$P _ j$ に $j$ 番目の商品を買う人数をかけたものです。

制約

• $1\\leq N\\leq2\\times10^5$
• $1\\leq M\\leq2\\times10^5$
• $0\\leq B _ i\\leq10^9\\quad(1\\leq i\\leq N)$
• $0\\leq C _ i\\leq10^9\\quad(1\\leq i\\leq M)$
• 入力はすべて整数

入力

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

$N$ $M$ $B _ 1$ $B _ 2$ $\\ldots$ $B _ N$ $C _ 1$ $C _ 2$ $\\ldots$ $C _ M$

出力

$j=1,2,\\ldots,M$ について、$j$ 番目の商品の売り上げを空白区切りで $1$ 行に出力せよ。

入力例 1

5 4
100 200 300 400 500
120 370 470 80

出力例 1

1280 2350 2850 1140

たとえば、$1$ 番目の商品の値段を $320$ にすると、$2,3,4,5$ 番目の客が購入します。 $1$ 番目の商品の売り上げは $1280$ になります。 $1$ 番目の商品の売り上げを $1280$ より大きくすることはできないので、$1$ 番目に出力すべき値は $1280$ です。

入力例 2

4 4
0 2 10 2
13 13 0 4

出力例 2

52 52 10 18

購買意欲が同じ $2$ 人や、商品価値が同じ $2$ 品があることもあります。

入力例 3

12 15
16 592 222 983 729 338 747 61 451 815 838 281
406 319 305 519 317 590 507 946 365 5 673 478 340 176 2

出力例 3

6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655

入力例 4

5 5
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 4

10000000000 10000000000 10000000000 10000000000 10000000000

売り上げが $32\\operatorname{bit}$ 整数におさまらない場合があることに注意してください。