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

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

Palindromic value of some string $w$ is defined as the total number of unique substrings of $w$ 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.

Input Specification

The first line contains an integer $n$ $(1\le n\le 100000)$, number of characters.

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

The $i^{\text{th}}$ of following $n-1$ lines contains two integers $a_i,b_i$ $(1\le a_i,b_i\le n,a_i\ne b_i)$ representing the $i^{\text{th}}$ concatenation.

Output Specification

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

Constraints

Subtask	Points	Constraints
$1$	$10$	$1\le n\le 100$
$2$	$20$	$1\le n\le 1000$
$3$	$30$	$a_i=1,b_i=i+1$ for all $i=1,2,\dots ,n-1$.
$4$	$50$	No additional constraints.

Sample Input 1

3
010
1 2
2 3

Sample Output 1

2
3

Sample Input 2

5
00111
4 1
1 5
2 1
3 1

Sample Output 2

2
3
4
5

Sample Input 3

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

Sample Output 3

2
2
2
3
4
6
8

Explanation for Sample Output 3

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 substrings: 0, 00, 000, 10001, 0100010, 1, 010, 00100.