Galaksija

Πριν από πολύ καιρό σε έναν γαλαξία πολύ, πολύ μακριά, υπήρχαν \(Ν\) πλανήτες. Υπήρχαν επίσης ~N-1~ διαπλανητικά μονοπάτια που συνέδεαν όλους τους πλανήτες (άμεσα ή έμμεσα). Με άλλα λόγια, το δίκτυο των πλανητών και των μονοπατιών σχημάτιζε ένα δέντρο. Επιπλέον, κάθε μονοπάτι απαριθμήθηκε με έναν ακέραιο που υποδήλωνε την περιέργεια του μονοπατιού.
Ένα ζευγάρι πλανητών ~A~, ~B~ είναι βαρετό αν ισχύει το εξής:

• Ο ~A~ και ο ~B~ είναι διαφορετικοί πλανήτες
• Το ταξίδι μεταξύ του πλανήτη ~A~ και του ~B~ είναι δυνατό χρησιμοποιώντας ένα ή περισσότερα διαπλανητικά μονοπάτια
• Το δυαδικό XOR της περιέργειας όλων των μονοπατιών σε αυτό το ταξίδι είναι ίσο με 0

Αλίμονο, οι καιροί έχουν αλλάξει και ένας κακός αυτοκράτορας κυβερνά τον γαλαξία. Αποφάσισε να χρησιμοποιήσει τη Δύναμη για να καταστρέψει όλα τα διαπλανητικά μονοπάτια με μια συγκεκριμένη σειρά.
Προσδιορίστε τον αριθμό των βαρετών ζευγών πλανητών πριν ο αυτοκράτορας ξεκινήσει την καταστροφή και μετά από κάθε καταστροφή.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 100\,000)~.
Καθεμία από τις ακόλουθες ~N-1~ γραμμές περιέχει τρεις ακέραιους ~A_i,\;B_i,\;Z_i\;(1 \leq A_i,\;B_i \leq N,\;0 \leq Z_i \leq 1\,000\,000\,000)~ που δηλώνουν ότι οι πλανήτες ~A_i~ και ~B_i~ συνδέονται άμεσα με ένα μονοπάτι της περιέργειας ~Z_i~. Η ακόλουθη γραμμή εισόδου περιέχει τη μετάθεση των πρώτων ~N-1~ ακεραίων που δηλώνουν τη σειρά με την οποία ο αυτοκράτορας καταστρέφει τα μονοπάτια. Εάν το ~i~-οστό στοιχείο της μετάθεσης είναι ~j~, τότε ο αυτοκράτορας κατέστρεψε τη διαδρομή μεταξύ των πλανητών ~A_j~ και ~B_j~ στο ~i~-οστό βήμα.

Έξοδος

Η έξοδος πρέπει να περιέχει ~N~ γραμμές, η k-οστή γραμμή να περιέχει τον αριθμό των βαρετών ζευγών ~A,\;B~ από την εργασία αφού ο αυτοκράτορας κατέστρεψε ακριβώς ~k-1~ μονοπάτια.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας ~20~% των συνολικών πόντων, θα κατέχει ~N \leq 1\,000~.
Σε περιπτώσεις δοκιμής αξίας τουλάχιστον ~30~% των συνολικών πόντων, η περιέργεια κάθε διαδρομής θα είναι ίση με 0.

Παραδείγματα

input

2
1 2 0
1

output

1
0

Επεξήγηση του 1ου παραδείγματος:

Πριν την καταστροφή, η διαδρομή μεταξύ των πλανητών 1 και 2 είναι βαρετή. Μετά την καταστροφή, το μονοπάτι μεταξύ τους δεν υπάρχει πια.

input

3
1 2 4
2 3 4
1 2

output

1
0
0

Επεξήγηση του 2ου παραδείγματος:

Πριν την καταστροφή, το ζευγάρι πλανητών ~(1,\;3)~ είναι βαρετό. Το ταξίδι μεταξύ 1 και 3 δεν είναι πλέον δυνατό μετά την πρώτη και μετά τη δεύτερη καταστροφή και κανένα από τα υπόλοιπα ζεύγη πλανητών δεν είναι βαρετό.

input

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

output

6
3
1
0

Επεξήγηση του 3ου παραδείγματος:

Παρατηρήστε ότι σε αυτό το παράδειγμα κάθε ζεύγος πλανητών με μια πιθανή διαδρομή μεταξύ τους είναι βαρετό επειδή όλα τα μονοπάτια έχουν την περιέργεια 0.