配点 : $600$ 点

問題文

高橋くんは 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$ 行に出力せよ。

5 4
100 200 300 400 500
120 370 470 80

1280 2350 2850 1140

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

4 4
0 2 10 2
13 13 0 4

52 52 10 18

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

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

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

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

10000000000 10000000000 10000000000 10000000000 10000000000

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