Cho hai cây (cây xanh và cây tím), mỗi cây gồm ~N~ đỉnh, ~N-1~ cạnh.

Trọng số các cạnh trong cùng một cây là đôi một khác nhau và nằm trong đoạn ~[1,2N-2]~.

Với mỗi cặp ~(X,Y), X < Y~:

• ~M_g(X,Y)~ là trọng số lớn nhất trên đường đi từ ~X~ đến ~Y~ trong cây xanh.

• ~M_p(X,Y)~ là trọng số lớn nhất trên đường đi từ ~X~ đến ~Y~ trong cây tím.

Yêu cầu: Với mọi giá trị ~i=1,2,3,\dots,2N-2~, hãy đếm số cặp ~(X,Y)~ sao cho

~M_g(X,Y)=i~ hoặc ~M_p(X,Y)=i~.

Nếu cả hai cùng bằng ~i~, cặp đó chỉ được tính một lần ~(1 \le i \le 2N-2)~.

Input

• Dòng đầu chứa số nguyên ~N~ ~(N \le 5 \cdot 10^5)~.

• ~N-1~ dòng tiếp theo, mỗi dòng chứa ~A,B,C~, mô tả cạnh xanh nối ~A~ và ~B~ có trọng số ~C~

• ~N-1~ dòng cuối cùng, mỗi dòng chứa ~U,V,W~, mô tả cạnh tím nối ~U~ và ~V~ có trọng số ~W~ ~(1 \le C,W \le 2N-2)~.

Chú ý: Các cạnh xanh và các cạnh tím đều tạo thành cây; trong mỗi cây, trọng số các cạnh là đôi một khác nhau.

Output

~2N-2~ số nguyên. Số thứ ~i~ là số cặp ~(X,Y)~ sao cho ~M_g(X,Y)=i~ hoặc ~M_p(X,Y)=i~.

Scoring

Sample Input 1

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

Sample Output 1

2 2 0 5 0 0

Notes

Có ~2~ cặp tại ~i=1~: ~(1,2), (1,4)~

Có ~2~ cặp tại ~i=2~: ~(2,3), (2,4)~

Có ~5~ cặp tại ~i=4~: ~(1,2), (1,3), (1,4), (2,4), (3,4)~.