Đại hội thiên hà

Ở một thiên hà xa xôi, nơi mà vị thần Eros cai quản đang tổ chức một đại hội thể thao quy mô toàn thiên hà. Cư dân trên tất cả các hành tinh đều có thể đăng ký tham gia. Thần Eros là người đứng ra chỉ huy và tổ chức đại hội diễn ra vào tháng sau. Để kì đại hội trở nên công bằng đối với tất cả mọi người, thần Eros quyết định ngăn chặn những hành tinh có thể gian lận với nhau. Thiên hà bao gồm \(N\) hành tinh và \(N-1\) con đường nối các hành tinh lại với nhau tạo thành một đồ thị dạng cây. Con đường thứ \(i\) kết nối trực tiếp hành tinh \(u_i\) với hành tinh \(v_i\) và trọng số của con đường này là \(w_i\). Một hành tinh có thể đến được bất kỳ hành tinh nào khác thông qua một số con đường. Chiều dài đường đi giữa 2 hành tinh bằng tổng \(xor\) trọng số của các con đường trên đường đi giữa 2 hành tinh đó.

Hai hành tinh có thể là 1 cặp gian lận với nhau nếu như độ dài đường đi giữa chúng bằng 0. Vì để tránh sự gian lận nên thần Eros quyết định sử dụng thần lực phá hủy lần lượt các con đường theo một thứ tự nhất định. Thần Eros quan tâm rằng sau khi mình phá hủy một con đường thì còn bao nhiêu cặp hành tinh có thể gian lận với nhau ?

Yêu cầu: Hãy giúp thần Eros xác minh điều đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N\leq 100000\)).

• Dòng thứ \(i\) trong số \(N-1\) dòng tiếp theo chứa 3 số nguyên \(u_i,v_i,w_i\) (\(1\leq u_i\leq v_i\leq N,0\leq w_i\leq 10^9\)) mô tả con đường thứ \(i\).

• Dòng tiếp theo chứa \(N-1\) số nguyên \(x_1,x_2,…,x_{N-1}\) thể hiện thứ tự phá huỷ các con đường. Số nguyên thứ \(i\) cho biết thần Eros sẽ phá hủy con đường thứ \(x_i\).

Output

• Gồm \(N\) dòng, dòng thứ \(i\) chứa một số nguyên là số cặp hành tinh có thể gian lận sau khi đã phá hủy \(i-1\) con đường theo thứ tự trên.

Example

3
1 2 4
2 3 4
1 2

1
0
0

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N\leq 1000\).

• Subtask \(2\) (\(30\%\) số điểm): \(w_1=w_2=\ldots=w_{N-1}=0\).