h386. Apples and Bananas
Tags :
Accepted rate : 6人/9人 ( 67% ) [非即時]

Content

There are apples and bananas and each of them has an integer weight between 1..k. Your task is to calculate for each weight w between 2...2k the number of ways we can choose an apple and a banana whose combined weight is w.

1 ≤ k,n,m ≤ 2*105

1 ≤ ai, bi ≤ k

Input

The first input line contains three integers kn and m: the number k, the number of apples and the number of bananas.

The next line contains n integers a1,a2,...,an :weight of each apple.

The last line contains m integers b1,b2,...,bn  :weight of each banana.

Output

For each integer w between 2…2k print the number of ways to choose an apple and a banana whose combined weight is w.

Sample Input #1
5 3 4
5 2 5
4 3 2 3
Sample Output #1
0 0 1 2 1 2 4 2 0

Hint ：

Explanation: For example for w = 8 there are 4 different ways: we can pick an apple of weight 5 in two different ways and a banana of weight 3 in two different ways.

Tags:

[管理者： linlincaleb@ ... (臨末之頌) ]

 ID User Problem Subject Hit Post Date 29719 fire5386 (becaidorz) h386 395 2022-03-24 22:12