CSES 2111 ↗

Apples and Bananas

For each combined weight `2..2k`, the number of apple/banana pairs with that total.

0
submissions
—
best score

There are n apples and m 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.

Input

The first input line contains three integers k, n 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,…,bm: 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.

Constraints

  • 1≤k,n,m≤2⋅105
  • 1≤ai≤k
  • 1≤bi≤k

Example

Input:

5 3 4
5 2 5
4 3 2 3

Output:

0 0 1 2 1 2 4 2 0  

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.

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/ApplesAndBananas/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.