A long time ago in a galaxy far, far away, there were ~N~ planets. There were also ~N-1~ interplanetary paths that connected all the planets (directly or indirectly). In other words, the network of planets and paths formed a tree. Additionally, each path was enumerated with an integer that denoted the curiosity of the path.

A pair of planets ~A, B~ is boring if the following holds:

• ~A~ and ~B~ are different planets
• travelling between planet ~A~ and ~B~ is possible using one or more interplanetary paths
• binary XOR of the curiosity of all the paths in that travel is equal to 0

Alas, the times have changed and an evil emperor is ruling the galaxy. He decided to use the Force to destroy all the interplanetary paths in a certain order.

Determine the number of boring pairs of planets before the emperor started the destruction and after each destruction.

Input

The first line of input contains the integer ~N~ ~(1 \le N \le 100\,000)~.

Each of the following ~N-1~ line contains three integers ~A_i~, ~B_i~, ~Z_i~ ~(1 \le A_i, B_i \le N, 0 \le Z_i \le 1\,000\,000\,000)~ that denote that planets ~A_i~ and ~B_i~ are directly connected with a path of curiosity ~Z_i~.

The following line of input contains the permutation of the first ~N-1~ integers that denote the order in which the emperor is destroying the paths. If the ~i^{th}~ element of the permutation is ~j~, then the emperor destroyed the path between planets ~A_j~ and ~B_j~ in the ~i^{th}~ step.

Output

The output must contain ~N~ lines, the ~k^{th}~ line containing the number of boring pairs ~A, B~ from the task after the emperor destroyed exactly ~k-1~ paths.

Scoring

In test cases worth 20% of total points, it will hold ~N \le 1\,000~.

In test cases worth at least 30% of total points, every path's curiosity will be equal to 0.

Sample Input 1

2
1 2 0
1

Sample Output 1

1
0

Explanation for Sample Output 1

Before the destruction, the path between planets 1 and 2 is boring. After destruction, the path between them doesn't exist anymore.

Sample Input 2

3
1 2 4
2 3 4
1 2

Sample Output 2

1
0
0

Explanation for Sample Output 2

Before the destruction, pair of planets ~(1, 3)~ is boring. Travel between 1 and 3 is no longer possible after the first and after the second destruction, and none of the remaining pairs of planets is boring.

Sample Input 3

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

Sample Output 3

6
3
1
0

Explanation for Sample Output 3

Notice that in this example each pair of planets with a possible path between them is boring because all paths have the curiosity 0.