Migrated from Lutece 2876 爱生活

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你所热爱的，就是你的生活。

Kanade 有一棵 $n$ 个节点的有根树，节点编号为 $1\ldots n$，根节点为 $1$。每个节点有一个权值 $a_i$。设树上两点有 $u,v\ (u\neq v)$ 且 $u$ 是 $v$ 的祖先，如果 $u,v$ 满足 $a_u>a_v$，则称有序数对 $(u,v)\in A_u$，若 $a_u=a_v$ 则称 $(u,v)\in B_u$，若 $a_u<a_v$ 则称 $(u,v)\in C_u$。其中，$A_u,B_u,C_u$ 为有序数对集。

对于每个节点 $i$，请求出 $|A_i|,|B_i|,|C_i|$ 的值。其中，对于集合 $A$，$|A|$ 表示集合的大小，也就是集合内元素个数。

Input

第一行一个正整数 $n\ (2\le n\le 2\times 10^5)$，表示树的节点数；

第二行 $n-1$ 个正整数 $f_i\ (1\le f_i\le n)$，第 $i$ 个正整数表示 $i+1$ 号节点的父节点为 $f_i$；

第三行 $n$ 个非负整数 $a_i\ (0\le a_i\le 10^9)$，第 $i$ 个非负整数为 $a_i$，表示 $i$ 号节点的权值。

Output

输出 $n$ 行，每行三个整数，第 $i$ 行输出的三个整数分别表示 $|A_i|,|B_i|,|C_i|$ 的值。

Samples

5
1 1 3 3
0 0 1 2 0

0 2 2
0 0 0
1 0 1
0 0 0
0 0 0

Note

样例如上图所示：

• 对于 $1$ 号节点，$A_1=\emptyset,B_1=\{(1,2),(1,5)\},C_1=\{(1,3),(1,4)\}$；
• 对于 $2$ 号节点，$A_2=B_2=C_2=\emptyset$；
• 对于 $3$ 号节点，$A_3=\{(3,5)\},B_3=\emptyset,C_3=\{(3,4)\}$；
• 对于 $4,5$ 号节点，$A_4=B_4=C_4=A_5=B_5=C_5=\empty$。

Resources

The 20th UESTC Programming Contest Preliminary