Boredom in the Galaxy

A long time ago, in a galaxy far, far away, there were \(n\) planets and \(n-1\) edges connecting them, forming a tree. Each edge has an associated weight.

A pair of distinct planets \((A, B)\) is called bored if and only if:

• \(A \neq B\).
• Planet \(A\) and planet \(B\) are in the same connected component.
• If one considers the unique simple path between \(A\) and \(B\), and computes the \(\operatorname{xor}\) of all edge weights on that path, the result is \(0\). In other words, if \(d(A,B)\) denotes the xor sum then \(d(A,B)=0\).

You are given the tree and a permutation representing the order in which the edges are destroyed. Your task is to report the number of bored pairs initially (with full connectivity) and then after each edge removal.

inputFormat

The first line contains an integer \(n\) \((2 \le n \le 10^5)\), the number of planets.

The next \(n-1\) lines each contain three integers \(u\), \(v\), and \(w\) representing an edge between planets \(u\) and \(v\) with weight \(w\). It is guaranteed that these edges form a tree.

The last line contains a permutation of \(1, 2, \dots, n-1\); the \(i\)th number indicates the index (1-indexed, in the order the edges were given) of the edge that is destroyed in the \(i\)th operation.

outputFormat

Output \(n\) integers separated by spaces. The first integer is the number of bored pairs in the initial tree. The \(i\)th integer (for \(1 \le i \le n-1\)) is the number of bored pairs after the first \(i\) edge removals.

sample

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

3 1 0 0