Task Palindromi

Σας δίνεται μια ακολουθία ~n~ χαρακτήρων 0 ή 1, με δείκτες αριθμούς ~1,\;2,\;\ldots,\;n~. Αρχικά κάθε χαρακτήρας αντιπροσωπεύει μια συμβολοσειρά μήκους ένα. Κατά τη διάρκεια μιας συνένωσης επιλέγονται δύο λέξεις ~a~ και ~b~, διαγράφονται και αντικαθίσταται από τη συμβολοσειρά ~ab~ έτσι ώστε οι χαρακτήρες του ~b~ να γράφονται μετά τους χαρακτήρες του ~a~.

Οι ~n~ αρχικές συμβολοσειρές ενώνονται σε μια τελική συμβολοσειρά χρησιμοποιώντας μια ακολουθία ~n - 1~ συνενώσεων. Η ~i~-οστή από αυτές τις συνενώσεις περιγράφεται από ένα ζεύγος δεικτών ~(a_i,\;b_i)~, που δηλώνει ότι η συμβολοσειρά που περιέχει τον ~a_i~-οστό χαρακτήρα και η συμβολοσειρά που περιέχει τον ~b_i~-οστό χαρακτήρα πρέπει να συνενωθούν. Είναι εγγυημένο ότι χαρακτήρες με δείκτες ~a_i~ και ~b_i~ δεν βρίσκονται στην ίδια συμβολοσειρά.

Η παλινδρομική τιμή κάποιας συμβολοσειράς ~w~ ορίζεται ως ο συνολικός αριθμός των μοναδικών υποσυμβολοσειρών του ~w~ που είναι παλίνδρομες. Ορίζουμε ως παλίνδρομα τις συμβολοσειρές που είναι ίδιες όταν διαβάζονται από αριστερά προς τα δεξιά και από τα δεξιά προς τα αριστερά. Μια υποσυμβολοσειρά μιας συμβολοσειράς ορίζεται ως μια συμβολοσειρά που λαμβάνεται διαγράφοντας μηδέν ή περισσότερων χαρακτήρων από την αρχή ή/και τέλος της συμβολοσειράς.

Για κάθε συνένωση εκτυπώστε την παλινδρομική τιμή της συμβολοσειράς που προκύπτει.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~n\;(1 \le n \le 100\,000)~, που είναι ο αριθμός των χαρακτήρων.

Στη δεύτερη γραμμή υπάρχει μια συμβολοσειρά με ~n~ χαρακτήρες 0 και 1 που αντιπροσωπεύουν τις αρχικές συμβολοσειρές.

Το i-οστό των παρακάτω ~n - 1~ γραμμών περιέχει δύο ακέραιους αριθμούς ~a_i~ και ~b_i\;(1 \le a_i,\;b_i \le n,\;a_i \ne b_i)~ που αντιπροσωπεύει την ~i~-οστή αλληλουχία.

Έξοδος

Εκτυπώστε ~n - 1~ γραμμές, τις παλινδρομικές τιμές των λέξεων που λαμβάνονται μετά από κάθε συνένωση.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n \le 100~.
2	20	~1 \le n \le 1000~.
3	30	~a_i\;=\;1,\;b_i\;=\;i + 1~ για όλα τα ~i\;=\;1,\;2,\;\ldots,\;n - 1~.
4	50	Κανένας επιπλέον περιορισμός.

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

input

3
010
1 2
2 3

output

2
3

input

5
00111
4 1
1 5
2 1
3 1

output

2
3
4
5

input

8
10010000
7 5
4 2
3 6
1 3
6 8
5 3
1 2

output

2
2
2
3
4
6
8

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

Οι συμβολοσειρές που δημιουργήθηκαν πρόσφατα μετά από κάθε συνένωση είναι: ~00,\;10,\;00,\;100,\;1000,\;001000~ και ~00100010~. Οι αντίστοιχες παλινδρομικές τιμές δίνονται στην έξοδο του παραδείγματος. Π.χ. η παλινδρομική τιμή του ~00100010~ είναι 8 επειδή η συμβολοσειρά περιέχει 8 παλίνδρομες υποσυμβολοσειρές: ~0,\;00,\;000,\;10001,\;0100010,\;1,\;010~ και ~00100~.