Palindromi

문제

You are given a sequence of $nn$ characters 0 or 1, indexed by numbers $1,2,\dots ,n1,\; 2,\; \backslash dots\; ,\; n$. Initially every character represents a string of length one. During a concatenation two words $aa$ and $bb$ are chosen, deleted, and replaced by the string $abab$ such that the characters of $bb$ are written after the characters of $aa$.

The $nn$ initial strings are concatenated to one final string using a sequence of $n-1n-1$ concatenations. The $ii$-th of those concatenation is described by a pair of indexes $(a_i,b_i)(a\_i\; ,\; b\_i)$, which denotes that the string containing $a_{i}a\_i$-th character and the string containing $b_{i}b\_i$-th character are to be concatenated. It is guaranteed that characters with indexes $a_{i}a\_i$ and $b_{i}b\_i$ are not in the same string.

Palindromic value of some string $ww$ is defined as the total number of unique substrings of $ww$ which are palindromes. We define palindromes as strings that are the same when read left to right and right to left. A substring of a string is defined as a string obtained by erasing zero or more characters from the beginning and/or ending of the string.

For every concatenation print the palindromic value of the resulting string.

입력

The first line contains an integer $nn$ (1 ≤ n ≤ 100\,000), number of characters.

In the second line there is a string of $nn$ characters 0 and 1 which represent the initial strings.

The $ii$-th of following $n-1n\; -\; 1$ lines contains two integers $a_{i}a\_i$ and $b_{i}b\_i$ (1 ≤ a_i , b_i ≤ n, $a_i\mathrm{\ne }{b}_{i}a\_i\; \backslash ne\; b\_i$) representing the $ii$-th concatenation.

출력

Print $n-1n\; -\; 1$ lines, the palindromic values of words obtained after each concatenation.

힌트

Clarification of the third example:

Newly created strings after every concatenation are: 00, 10, 00, 100, 1000, 001000 and 00100010. Their respective palindromic values are given in the example output. E. g. the palindromic value of 00100010 is 8 because the string contains 8 palindromic substring: 0, 00, 000, 10001, 0100010, 1, 010 and 00100.

3
010
1 2
2 3

2
3

5
00111
4 1
1 5
2 1
3 1

2
3
4
5

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

2
2
2
3
4
6
8