Problem Description

Farmer John has N cows numbered sequentially from 1 to N (2 ≤ N ≤ 10^5), and their relationships can be described using a tree structure. Unfortunately, a disease is spreading among them.

Initially, some cows are infected. Each night, infected cows spread the disease to their neighbors. Once a cow is infected, it remains infected. After several nights, Farmer John realizes the situation and conducts tests to determine which cows are infected.

You are given Q (1 ≤ Q ≤ 20) different numbers of nights, each within the range [0, N]. For each number of nights, determine the minimum number of cows that could have been initially infected, or report that the number of nights is inconsistent with the given information.

Input Format

The first line contains an integer N.

The next line contains a bit string of length N consisting of 1s and 0s, where 1 indicates an infected cow and 0 indicates a cow that remains uninfected after several nights.

The following N-1 lines describe the edges of the tree.

The next line contains Q and Q numbers of nights.

Output Format

Output Q lines, each containing the answer for the corresponding number of nights. If there is no solution, output -1.

Sample Input and Output

Input Sample #1

5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0

Output Sample #1

1
1
1
1
2
5

Input Sample #2

10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10

Output Sample #2

10
3
2
1
1
1
1
1
1
1
1

Input Sample #3

5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5

Output Sample #3

3
1
1
-1
-1
-1

Notes

Sample Explanation 1

For the first four queries, one possibility is that only cow 3 was initially infected. For the fifth query (1 night), one possibility is that cows 2 and 4 were initially infected. For the sixth query (0 nights), one possibility is that all five cows were initially infected.

Sample Explanation 2

For the first query (0 nights), one possibility is that all ten cows were initially infected. For the second query (1 night), one possibility is that cows 2, 7, and 9 were initially infected. For the third query (2 nights), one possibility is that cows 2 and 9 were initially infected. For the fourth to eleventh queries, one possibility is that only cow 7 was initially infected.

Sample Explanation 3

For the first query (0 nights), one possibility is that cows 1, 2, and 3 were initially infected. For the second query (1 night), one possibility is that only cow 2 was initially infected. For the third query (2 nights), one possibility is that only cow 1 was initially infected. For the fourth to sixth queries, it is impossible to satisfy the given conditions.

Test Case Properties

• Test cases 4-5 satisfy N ≤ 10.
• Test cases 6-8 satisfy all cows are infected.
• Test cases 9-11 satisfy N ≤ 400.
• Test cases 12-23 have no additional restrictions.

见题面 Input 部分

见题面 Output 部分