Statement

Alice and Bob have huge dice where the possible roll values are from ~0~ to ~N~ (inclusive).

These huge dice have many many faces. In particular, Alice's die has ~A_i~ faces with roll value ~i~, while Bob's die has ~B_j~ faces with roll value ~j~.

Alice and Bob roll their dice at the same time. Their score is the sum of their roll values. Alice and Bob are wondering: for each of the possible scores ~s~ from ~0~ to ~2N~ (inclusive), how many different ways could they have have rolled the score ~s~?

Two ways are considered different if Alice rolls a different face or Bob rolls a different face, regardless of their value.

Constraints

• ~1 \leq N \leq 10^6~
• ~1 \leq A_i, B_j \leq 10^6~

Input Specification

The first line of input will contain ~N~.

The second line of input will contain ~N + 1~ space-separated integers, ~A_0, A_1, \dots A_N~.

The third line of input will contain ~N + 1~ space-separated integers, ~B_0, B_1, \dots B_N~.

Output Specification

One line containing space-separated ~2N + 1~ integers, the number of ways that a score of ~0, 1, 2, \dots 2N~ can be rolled.

Sample Input 1

3
1 2 3 4
5 6 7 8

Sample Output 1

5 16 34 60 61 52 32

Explanation for Sample 1

The fifth number in the output, ~61~, represents the number of ways to get a score of ~4~.

There are ~3~ cases of this happening:

1. Alice rolls a ~1~ and Bob rolls a ~3~. Alice has ~2~ faces with value ~1~ and Bob has ~8~ faces with value ~3~. There are ~2 \times 8 = 16~ ways to roll a ~3~ in this case.

2. Alice rolls a ~2~ and Bob rolls a ~2~. Alice has ~3~ faces with value ~2~ and Bob has ~7~ faces with value ~2~. There are ~3 \times 7 = 21~ ways to roll a ~3~ in this case.

3. Alice rolls a ~3~ and Bob rolls a ~1~. Alice has ~4~ faces with value ~3~ and Bob has ~6~ faces with value ~1~. There are ~4 \times 6 = 24~ ways to roll a ~3~ in this case.

The total of these cases is ~61~.

Sample Input 2

15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Sample Output 2

17 52 106 180 275 392 532 696 885 1100 1342 1612 1911 2240 2600 2992 3095 3164 3198 3196 3157 3080 2964 2808 2611 2372 2090 1764 1393 976 512