Emotions flying at high speed in the air turn into wind, and we chase each other...

Nannan happily started a relationship $n$ days ago. During these $n$ days, she had a romantic gain $a_i$ ($|a_i| \le 1$) and a romantic experience $b_i$ each day. Of course, arguments may occur in a relationship, and the relationship may also lead to a decrease in intelligence, so both $a_i$ and $b_i$ can be negative.

Nannan is a thoughtful girl. She can choose a continuous period of days out of these $n$ days to obtain a "positive memory" and a "negative reflection." Specifically, if she chooses $l, r$ such that $1 \le l \le r \le n$, this can form a positive memory with a gain value of $\sum_{i=l}^r a_i$ and an experience value of $\sum_{i=l}^r b_i$, or a negative reflection with a gain value of $-\sum_{i=l}^r a_i$ and an experience value of $-\sum_{i=l}^r b_i$.

We collectively refer to positive memories and negative reflections as "memories." Clearly, Nannan has a total of $n(n+1)$ memories, and the gain values of these memories all fall within the interval $[-n, n]$.

Only memories with an experience value greater than $0$ are "good memories." Now, Nannan wants to know, for each $i \in [-n, n]$, how many good memories have a gain value of $i$.

Input

The first line contains a positive integer $n$. The second line contains $n$ integers, representing $a_1, \dots, a_n$. The third line contains $n$ integers, representing $b_1, \dots, b_n$.

Output

A single line containing $2n+1$ integers, representing the number of good memories with gain values of $-n, \dots, n$, respectively.

Examples

Input 1

3
1 1 1
1 -2 3

Output 1

0 1 1 0 2 1 1

Input 2

5
1 1 -1 -1 1
1 -2 3 -4 5

Output 2

0 0 0 1 3 4 6 1 0 0 0

Constraints

For 20% of the data, $1 \le n \le 1000$; For 60% of the data, $1 \le n \le 50000$; For 100% of the data, $1 \le n \le 10^5$, $|a_i| \le 1$, $|b_i| \le 10^9$.