Problem Description

You are given a $\texttt{01}$ sequence of length $n$ with indices $1, 2, \dots, n$. Initially, each character represents a string of length $1$. In a concatenation operation, you need to select two strings $a$ and $b$, delete them, and replace them with the string $ab$, which is formed by writing all characters of $a$ followed by all characters of $b$.

These $n$ initial strings need to be concatenated into one string using $n-1$ concatenation operations. The $i$-th operation is described by a pair of indices $(a_i, b_i)$, indicating that the strings containing the characters at indices $a_i$ and $b_i$ are to be concatenated. It is guaranteed that the characters at indices $a_i$ and $b_i$ are not in the same string.

The palindromic value of a string $w$ is defined as the number of distinct palindromic substrings in $w$. A palindromic string is one that reads the same forwards and backwards. A substring is defined as a string that can be obtained by deleting one or more characters from the beginning and/or end of the original string.

For each concatenation operation, output the palindromic value of the resulting string.

Input Format

The first line contains an integer $n$, the number of characters.

The second line contains a $\texttt{01}$ string of length $n$, representing the initial strings.

The next $n-1$ lines each contain two integers $a_i$ and $b_i$, describing the $i$-th concatenation operation.

Output Format

Output $n-1$ lines, each representing the palindromic value of the string obtained after each concatenation operation.

Sample Input and Output

Input Sample #1

3
010
1 2
2 3

Output Sample #1

2
3

Input Sample #2

5
00111
4 1
1 5
2 1
3 1

Output Sample #2

2
3
4
5

Input Sample #3

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

Output Sample #3

2
2
2
3
4
6
8

Notes

Sample Explanation 3:

The strings created after each concatenation are: $\tt 00, 10, 00, 100, 1000, 001000$ and $\tt 00100010$.

Their respective palindromic values are given in the sample output. For example, the palindromic value of $\tt 00100010$ is $8$ because the string contains $8$ palindromic substrings: $\tt 0, 00, 000, 10001, 0100010, 1010$ and $00100$.

Data Range:

For $9\%$ of the data: $1 \le n \le 100$

For $18\%$ of the data: $1 \le n \le 1000$

For $27\%$ of the data: $a_i = 1, b_i = i + 1$

For $100\%$ of the data: $1 \le n \le 10^5$, $1 \le a_i, b_i \le n$

This problem has the same scoring as COCI 2021-2022#6, with a maximum score of $110$ points.

见题面 Input 部分

见题面 Output 部分