• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

A long time ago in the University of Tehran, there were $N$ buildings. There were also $N-1$ pathways that connected all the buildings (directly or indirectly). In other words, the network of buildings and paths formed a tree. Additionally, each path was enumerated with an integer that denoted the curiosity of the path.

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

• A and B are different buildings
• travelling between building A and B is possible using one or more pathways
• binary XOR of the curiosity of all the paths in that travel is equal to 0

Unfortunately, times have changed, and an evil dean named Zein is now ruling the department. He decided to use the Force to destroy all the pathways in a certain order. Determine the number of boring pairs of buildings before Zein started the destruction and after each destruction.

Input

The first line of input contains the integer N.

Each of the following $N-1$ line contains three integers $a_i$, $b_i$, $z_i$, that denote that buildings $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 Zein is destroying the paths. If the $i^{th}$ element of the permutation is j, then Zein destroyed the path between buildings $a_i$ and $b_i$ 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 Zein destroyed exactly $k-1$ paths.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq a_i,b_i \leq N$
• $0 \leq z_i \leq 10^9$

Sample Test Data

input 1

3
1 2 5
2 3 5
2 1

output 1

1
0
0

input 2

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

output 2

6
3
1
0