I. 子树 mex
time limit per test
3 秒
memory limit per test
512 MB
input
标准输入
output
标准输出

给定一棵 n 个点的树，1 号点为根节点，i 号点的点权为 ai。

对 i = 1, 2, ..., n 都求：以 i 号点为根的子树内所有节点点权之集的 。

其中 的定义为可重集 S 中未出现的最小非负整数，例如 ，。

Input

输入共三行。

第一行，输入一个整数 n (1 ≤ n ≤ 5 × 105)，表示树的节点总数。

第二行，输入 n - 1 个整数 fi (2 ≤ i ≤ n,  1 ≤ fi < i)，表示 i 号点的父节点为 fi。

第三行，输入 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 109)，表示节点点权。

Output

输出共一行，n 个以空格相隔的整数，表示 号点的子树内点权之集的 。

Example
Input
8
1 1 1 2 2 3 7
1 2 3 5 0 1 0 2
Output
4 3 1 0 1 0 1 0
Note

样例解释如下：

  • 1 号点的子树内点权之集为 S1 = {1, 2, 3, 5, 0, 1, 0, 2}，。
  • 2 号点的子树内点权之集为 S2 = {2, 0, 1}，。
  • 3 号点的子树内点权之集为 S3 = {3, 0, 2}，。
  • 4 号点的子树内点权之集为 S4 = {5}，。
  • 5 号点的子树内点权之集为 S5 = {0}，。
  • 6 号点的子树内点权之集为 S6 = {1}，。
  • 7 号点的子树内点权之集为 S7 = {0, 2}，。
  • 8 号点的子树内点权之集为 S8 = {2}，。

因此输出为 4 3 1 0 1 0 1 0。