Cow Checkups

문제

Note: We suggest using a language other than Python to earn full credit on this problem.

Farmer John's $NN$ ($1\le N\le 75001\; \backslash leq\; N\; \backslash leq\; 7500$) cows are standing in a line, with cow $11$ at the front of the line and cow $NN$ at the back of the line. FJ's cows also come in many different species. He denotes each species with an integer from $11$ to $NN$. The $ii$'th cow from the front of the line is of species $a_{i}a\_i$ ($1\le a_i\le N1\; \backslash leq\; a\_i\; \backslash leq\; N$).

FJ is taking his cows to a checkup at a local bovine hospital. However, the bovine veterinarian is very picky and wants to perform a checkup on the $ii$'th cow in the line, only if it is of species $b_{i}b\_i$ ($1\le b_i\le N1\; \backslash leq\; b\_i\; \backslash leq\; N$).

FJ is lazy and does not want to completely reorder his cows. He will perform the following operation exactly once.

• Select two integers $ll$ and $rr$ such that $1\le l\le r\le N1\; \backslash leq\; l\; \backslash le\; r\; \backslash leq\; N$. Reverse the order of the cows that are between the $ll$-th cow and the $rr$-th cow in the line, inclusive.

FJ wants to measure how effective this approach is. For each $c=0\dots Nc=0\; \backslash ldots\; N$, help FJ find the number of distinct operations ($l,rl,r$) that result in exactly $cc$ cows being checked. Two operations ($l_1,r_{1}l\_1,r\_1$) and ($l_2,r_{2}l\_2,r\_2$) are different if $l_1\mathrm{\ne }{l}_{2}l\_1\; \backslash neq\; l\_2$ or $r_1\mathrm{\ne }{r}_{2}r\_1\; \backslash neq\; r\_2$.

입력

The first line contains an integer $NN$.

The second line contains $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash ldots,\; a\_N$.

The third line contains $b_1,b_2,\dots ,b_{N}b\_1,\; b\_2,\; \backslash ldots,\; b\_N$.

출력

Output $N+1N+1$ lines with the $ii$-th line containing the number of distinct operations ($l,rl,r$) that result in $i-1i-1$ cows being checked.

3
1 3 2
3 2 1

3
3
0
0

3
1 2 3
1 2 3

0
3
0
3

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

0
6
14
6
2
0
0
0