JanuszPol 是一家拥有悠久历史的波兰公司。然而最近，公司陷入了严重的财务困境，最终被一家外国竞争对手收购。新董事会决定彻底重组公司架构。在此之前，公司采用的是典型的树状结构：

• 恰好有一名执行董事，他没有上级。
• 其他每名员工都恰好有一名直接上级，且不存在循环关系。

对于每名员工 $x$，他们的下属是指所有在树中位于 $x$ 下方的员工 $y$（即存在一条从 $y$ 到 $x$ 的直接上级序列）。

收购完成后，公司将继续雇佣相同的人员，并同样以树状结构组织，但每名员工都会被分配到不同的职位，因此树的形态可能会发生彻底改变。不过，执行董事的职位保证不变。现在每个人都害怕给别人下达命令——因为随时随地，下属都可能变成上级……

给定收购前后两棵树的描述，对于每名员工 $x$，确定在收购前是 $x$ 的下属，且在收购后依然是 $x$ 的下属的人数。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)：员工人数。员工编号从 $1$ 到 $n$，其中 $1$ 号员工为执行董事。第二行包含收购前的公司结构：有 $n-1$ 个数字 $a_2, a_3, \dots, a_n$，其中 $a_i$ 是 $i$ 的上级。第三行同样包含 $n-1$ 个数字 $b_2, b_3, \dots, b_n$，其中 $b_i$ 是收购后 $i$ 的上级。你可以假设两份描述都定义了以 $1$ 为根的合法树。

输出格式

输出一行，包含 $n$ 个数字，其中第 $i$ 个数字表示在两棵树中同时是 $i$ 的下属的人数。

子任务

样例

输入格式 1

5
1 1 3 3
1 2 3 1

输出格式 1

4 0 1 0 0