题目描述

小可可的$N$个玩具（$1 \leq N \leq 7500$）排成一列，玩具1在最前面，玩具$N$在最后面。每个玩具有一个编号$a_i$（$1 \leq a_i \leq N$）。

玩具医院只会在第$i$个玩具的编号为$b_i$时为一次匹配。小可可可以执行以下操作恰好一次：

选择区间$[l,r]$（$1 \leq l \leq r \leq N$），反转该区间内玩具的顺序。

对于每个$c=0...N$，计算能使恰好$c$个玩具被匹配的不同操作$(l,r)$的数量。

输入格式

• 第一行：整数$N$
• 第二行：$a_1,a_2,...,a_N$
• 第三行：$b_1,b_2,...,b_N$

输出格式

输出$N+1$行，第$i$行表示$c=i-1$时的操作数量。

样例

样例#1

输入

3
1 3 2
3 2 1

输出

3
3
0
0

样例#2

输入

3
1 2 3
1 2 3

输出

0
3
0
3

样例#3

输入

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

输出

0
6
14
6
2
0
0
0

数据范围

• 测试点4-6：$N \leq 100$
• 测试点7-13：无特殊限制

样例解释

样例#1说明

• 不反转任何区间时（$l=r$），0个玩具匹配
• 反转[1,2]使第1个匹配
• 反转[2,3]使第2个匹配
• 反转[1,3]使第3个匹配

样例#2说明

• 不反转时3个都匹配
• 其他反转都会减少匹配数

样例#3说明

• 特定反转区间可以产生4个匹配的情况