Farmer John 有 $N$ ($2\le N\le 10^5$) 头奶牛，编号为 $1\dots N$，奶牛之间的连接关系构成一棵树。不幸的是，一种疾病正在蔓延。

最初，一些奶牛被感染。每天晚上，被感染的奶牛会将疾病传染给它们的邻居。一旦奶牛被感染，它将保持感染状态。经过若干个夜晚后，Farmer John 意识到了这个问题，于是他检测了奶牛以确定谁患有疾病。

给定 $Q$ ($1\le Q\le 20$) 个不同的夜晚数量，每个值都是 $[0,N]$ 范围内的整数。对于每个夜晚数量，请确定最初可能患病的奶牛的最少数量；如果该夜晚数量与给定信息不符，则输出 $-1$。

输入格式

第一行包含 $N$。

下一行包含一个长度为 $N$ 的位串，如果第 $i$ 头奶牛被感染，则第 $i$ 位为 1，否则为 0。至少有一头奶牛被感染。

接下来的 $N-1$ 行包含树的边。

然后是 $Q$，接着是 $Q$ 个夜晚数量的值。

输出格式

输出 $Q$ 行，分别为每个夜晚数量的答案，如果不可能，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

1
1
1
1
2
5

对于前四个询问，一种可能性是只有 3 号奶牛最初患病。对于第五个询问（1 个夜晚），一种可能性是 2 号和 4 号奶牛最初患病。对于第六个询问（0 个夜晚），一种可能性是所有五头奶牛最初都患病。

样例输入 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

样例输出 2

10
3
2
1
1
1
1
1
1
1
1

对于第一个询问（0 个夜晚），一种可能性是所有十头奶牛最初都患病。对于第二个询问（1 个夜晚），一种可能性是 2 号、7 号和 9 号奶牛最初患病。对于第三个询问（2 个夜晚），一种可能性是 2 号和 9 号奶牛最初患病。对于第四到第十一个询问，一种可能性是只有 7 号奶牛最初患病。

样例输入 3

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

样例输出 3

3
1
1
-1
-1
-1

对于第一个询问（0 个夜晚），一种可能性是 1 号、2 号和 3 号奶牛最初患病。对于第二个询问（1 个夜晚），一种可能性是只有 2 号奶牛最初患病。对于第三个询问（2 个夜晚），一种可能性是只有 1 号奶牛最初患病。对于第四到第六个询问，不存在符合条件的情况。

子任务

• 输入 4-5：$N \le 10$
• 输入 6-8：所有奶牛都被感染。
• 输入 9-11：$N \le 400$
• 输入 12-23：无额外限制。

题目来源：Suhas Nagar 和 Brandon Wang