Concatenation and Palindromic Substrings

You are given a binary 01 sequence of length \(n\) with indices \(1,2,\dots,n\). Initially, each character represents a string of length 1. In one concatenation operation, you must choose two strings \(a\) and \(b\) (which are guaranteed to be different, i.e. they do not belong to the same current string) and merge them by deleting both and replacing them with the string \(ab\) (i.e. write all characters from \(a\) followed by all characters from \(b\)).

The initial \(n\) strings are merged into one string by exactly \(n-1\) concatenation operations. The \(i\)th operation is described by a pair \((a_i, b_i)\) meaning that you choose the string that currently contains the character with index \(a_i\) as \(a\) and the string that contains the character with index \(b_i\) as \(b\).

A palindromic substring is defined as a contiguous substring which reads the same forwards and backwards. The palindrome value of a string \(w\) is defined as the number of distinct palindromic substrings of \(w\). For each concatenation operation, output the palindrome value of the string formed in that operation.

Note: A substring is obtained by deleting zero or more characters from the beginning and/or the end of the string.

inputFormat

The first line contains an integer \(n\) \( (1 \le n \le \text{some moderate limit})\). The second line contains a binary string of length \(n\) consisting of characters '0' and '1'.

The following \(n-1\) lines each contain two integers \(a_i\) and \(b_i\) (\(1 \le a_i, b_i \le n\)), describing an operation. It is guaranteed that at the moment of the operation, the characters at positions \(a_i\) and \(b_i\) belong to different strings.

outputFormat

Output \(n-1\) lines. The \(i\)th line should contain a single integer representing the palindrome value (i.e. the number of distinct palindromic substrings) of the string generated after the \(i\)th concatenation operation.

sample

3
101
1 2
2 3

2
3