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 100\,000)~, 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 1\,000~
~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.