You are given a sequence of characters, 0
or 1
, indexed by numbers . Initially, every character
represents a string of length one. During a concatenation, two words, and , are chosen, deleted, and
replaced by the string such that the characters of are written after the characters of .
The initial strings are concatenated to one final string using a sequence of concatenations. The of those concatenation is described by a pair of indices , which denotes that the string containing character and the string containing character are to be concatenated. It is guaranteed that characters with indices and are not in the same string.
Palindromic value of some string is defined as the total number of unique substrings of 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 , number of characters.
In the second line, there is a string of characters 0
and 1
which represent the initial strings.
The of following lines contains two integers representing the concatenation.
Output Specification
Print lines, the palindromic values of words obtained after each concatenation.
Constraints
Subtask | Points | Constraints |
---|---|---|
for all . | ||
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 because the string contains palindromic substrings: 0
, 00
, 000
, 10001
, 0100010
, 1
, 010
, 00100
.
Comments