给你一个长度为 $n$ 的字符序列，字符仅由 0 或 1 组成，下标为 $1, 2, \dots, n$。初始时，每个字符都代表一个长度为 $1$ 的字符串。在一次合并操作中，选择两个单词 $a$ 和 $b$，将它们删除，并用字符串 $ab$ 代替（即把 $b$ 的字符拼接在 $a$ 的字符后面）。

通过一系列共 $n-1$ 次合并操作，这 $n$ 个初始字符串最终会被合并为一个字符串。第 $i$ 次合并由一对下标 $(a_i, b_i)$ 描述，表示将包含第 $a_i$ 个字符的字符串与包含第 $b_i$ 个字符的字符串进行合并。保证下标为 $a_i$ 和 $b_i$ 的字符当前不在同一个字符串中。

一个字符串 $w$ 的回文值定义为 $w$ 中所有本质不同的回文子串的总数。我们定义回文串为从左往右读和从右往左读完全相同的字符串。字符串的子串定义为通过从字符串的开头和/或结尾删除零个或多个字符而得到的字符串。

对于每一次合并操作，输出合并后得到的新字符串的回文值。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 100\,000$），表示字符的数量。

第二行包含一个由 $n$ 个字符 0 和 1 组成的字符串，表示初始的字符串。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \neq b_i$），表示第 $i$ 次合并操作。

输出格式

输出 $n-1$ 行，每行一个整数，表示每次合并后得到的新字符串的回文值。

数据范围

样例

输入样例 1

3
010
1 2
2 3

输出样例 1

2
3

输入样例 2

5
00111
4 1
1 5
2 1
3 1

输出样例 2

2
3
4
5

输入样例 3

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

输出样例 3

2
2
2
3
4
6
8

说明

第三个样例的解释：

每次合并后新创建的字符串依次为：00、10、00、100、1000、001000 和 00100010。它们对应的回文值如样例输出所示。

例如，00100010 的回文值为 $8$，因为该字符串包含 $8$ 个本质不同的回文子串：0、00、000、10001、0100010、1、010 和 00100。