很久以前，在遥远的星系中，有 $N$ 颗行星。还有 $N - 1$ 条星际航道连接着所有的行星（直接或间接）。换句话说，行星和航道构成的网络是一棵树。此外，每条航道都有一个整数，表示该航道的“好奇值”。

如果满足以下条件，则称一对行星 $A, B$ 是“无聊的”：

• $A$ 和 $B$ 是不同的行星。
• 可以通过一条或多条星际航道在行星 $A$ 和 $B$ 之间旅行。
• 旅行路径上所有航道好奇值的二进制异或和等于 0。

然而，时代变了，一位邪恶的皇帝统治了星系。他决定使用原力按某种顺序摧毁所有的星际航道。

请确定在皇帝开始摧毁之前，以及每次摧毁之后，无聊的行星对的数量。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)。

接下来的 $N - 1$ 行，每行包含三个整数 $A_i, B_i, Z_i$ ($1 \le A_i, B_i \le N$, $0 \le Z_i \le 1\,000\,000\,000$)，表示行星 $A_i$ 和 $B_i$ 之间有一条直接相连的航道，其好奇值为 $Z_i$。

最后一行包含前 $N - 1$ 个正整数的一个排列，表示皇帝摧毁航道的顺序。如果该排列的第 $i$ 个元素是 $j$，则表示皇帝在第 $i$ 步摧毁了行星 $A_j$ 和 $B_j$ 之间的航道（即输入中给出的第 $j$ 条航道）。

输出格式

输出必须包含 $N$ 行，其中第 $k$ 行包含在皇帝摧毁了恰好 $k - 1$ 条航道后，满足题目要求的无聊行星对 $A, B$ 的数量。

数据范围

• 在占总分 20% 的测试数据中，满足 $N \le 1000$。
• 在占总分至少 30% 的测试数据中，每条航道的好奇值都等于 0。

样例

输入样例 1

2
1 2 0
1

输出样例 1

1
0

输入样例 2

3
1 2 4
2 3 4
1 2

输出样例 2

1
0
0

输入样例 3

4
1 2 0
2 3 0
2 4 0
3 1 2

输出样例 3

6
3
1
0

说明

样例 1 说明：在摧毁之前，行星 1 和 2 之间的路径是无聊的。摧毁之后，它们之间的路径不再存在。

样例 2 说明：在摧毁之前，行星对 $(1, 3)$ 是无聊的。在第一次和第二次摧毁之后，1 和 3 之间不再连通，且剩余的行星对中没有无聊的。

样例 3 说明：请注意，在此样例中，由于所有航道的好奇值均为 0，因此任何存在连通路径的行星对都是无聊的。