为了吸引更多游客并为马里博尔（Maribor）曾经引以为傲但如今已基本废弃的工业区带来资金，该市在原 Metalna 工厂（马里博尔在 20 世纪 90 年代初被迫倒闭的众多大型企业之一）的旧址上建造了一条赛道。赛道构建成一棵包含 $n$ 个顶点的有根树。树的顶点编号为 $0, 1, \dots, n - 1$，其中根节点的编号为 $0$。

比赛开始！起初，树的某些顶点上有赛车。每一秒，每辆车都会向着根节点方向移动到相邻的顶点。在任何时刻，如果两辆或多辆车同时到达同一个编号大于 $0$ 的顶点，它们就会发生碰撞，并无法继续参加比赛。对于顶点 $0$（根节点），此规则不适用；根节点在任何时刻都可以容纳任意数量的赛车。

对于每个顶点 $v$，输出整数 $c_v$，其定义如下： 如果比赛开始时顶点 $v$ 上没有赛车，则 $c_v = -1$。 否则，如果从顶点 $v$ 出发的赛车在前往根节点的途中发生碰撞，则 $c_v = -1$。 * 否则，$c_v$ 为从顶点 $v$ 出发的赛车到达根节点的时间。

输入格式

第一行包含一个整数 $n$，表示树的顶点数。

第二行包含 $n - 1$ 个整数，即 $p_1, p_2, \dots, p_{n-1}$。对于每个 $i \in \{1, \dots, n - 1\}$，$p_i$ 表示顶点 $i$ 的父节点；满足 $0 \le p_i < i$。

第三行包含 $n$ 个整数，即 $a_0, a_1, \dots, a_{n-1}$。对于每个 $i \in \{0, \dots, n - 1\}$，$a_i$ 为 $0$ 或 $1$。如果比赛开始时顶点 $i$ 上有赛车，则 $a_i = 1$；否则 $a_i = 0$。

输出格式

在一行中输出整数 $c_0, c_1, \dots, c_{n-1}$，并用空格分隔。

数据范围

• $1 \le n \le 10^6$。

子任务

1. (3 分) $n \le 3$。
2. (5 分) 对于每个 $i \in \{1, \dots, n - 1\}$，$p_i = i - 1$。
3. (8 分) $n \le 500$。
4. (9 分) $n \le 3000$。
5. (10 分) $n \le 10^5$。
6. (9 分) $p_i = \lfloor \frac{i-1}{2} \rfloor$。
7. (14 分) $n \le 2 \cdot 10^5$。
8. (19 分) 每个顶点最多有 3 个邻居（即根节点最多有 3 个子节点，所有其他顶点最多有 2 个子节点）。
9. (23 分) 无附加限制。

样例

输入 1

5
0 1 1 3
0 1 1 1 1

输出 1

-1 1 -1 -1 3

说明

比赛开始时，顶点 $0$（根节点）没有赛车。从顶点 $1$ 出发的赛车到达根节点需要 $1$ 秒，从顶点 $4$ 出发的赛车到达根节点需要 $3$ 秒。从顶点 $2$ 和 $3$ 出发的赛车在前往根节点的途中发生碰撞（发生在节点 $1$）。