Cách đây rất lâu trong một thiên hà xa có N hành tinh. Ngoài ra còn có N - 1 con đường kết nối tất cả các hành tinh (trực tiếp hoặc gián tiếp). Nói cách khác, mạng lưới các hành tinh và những con đường tạo thành một cây. Ngoài ra, mỗi con đường dẫn liệt kê với một số nguyên biểu thị sự tò mò của con đường.

Một cặp hành tinh A, B thật nhàm chán nếu những điều sau đây là:

• A và B là các hành tinh khác nhau

• Đường đi giữa hành tinh A và B có thể sử dụng một hoặc nhiều đường

• XOR nhị phân của sự tò mò của tất cả các con đường đó bằng 0

Than ôi, thời thế đã thay đổi và một hoàng đế độc ác đang cai trị thiên hà. Ông ta quyết định sử dụng Thần lực để phá hủy tất cả các con đường nối các hành tinh theo một thứ tự nhất định.

Bạn hãy xác định số lượng cặp hành tinh nhàm chán trước khi hoàng đế bắt đầu sự hủy diệt và sau khi mỗi lần phá hủy.

DLV: GALAKSIJA.INP

• Dòng đầu tiên của đầu vào chứa số nguyên N (1 <= N <= 100 000).

• Mỗi dòng trong số N - 1 dòng sau chứa ba số nguyên Ai, Bi, Zi (1 <= Ai; Bi <= N, 0 <=Zi <= 1 000 000 000) biểu thị rằng hành tinh Ai và Bi được kết nối trực tiếp với một con đường tò mò Zi.

• Dòng sau chứa hoán vị của N - 1 số nguyên đầu tiên biểu thị thứ tự trong đó hoàng đế đang phá hủy các con đường. Nếu phần tử của hoán vị là j, thì hoàng đế đã phá hủy con đường giữa hai hành tinh Aj và Bj trong cùng một bước.

-DLR: GALAKSIJA.OUT

Đầu ra phải chứa N dòng, dòng thứ k chứa số cặp hành tinh buồn chán A, B từ nhiệm vụ sau khi hoàng đế phá hủy đúng k - 1 con đường.

Ràng buộc:

• 20% tổng số điểm, nó sẽ giữ N <= 1 000.
• 30% tổng số điểm, sự tò mò của mọi con đường sẽ bằng 0

Sample INput

2
1 2 0
1

Sample Output

1
0