Background

Description

给定一棵有 n 个节点的无根树，每个节点上是一个字符，要么是(，要么是)。 定义 S(x, y) 为从 x 开始沿着最短路走到 y，将沿途经过的点上的字符依次连起来得到的字符串。 合法括号序定义如下: 1，()是合法的。 2，若A，合法，则(A)也合法。 3，若A，B 分别合法，则 AB 也合法。 函数 f(x, y) 等于对 S(x, y) 进行划分，使得每一个部分都是合法括号序，能得到的最大的段数，比如(())()()的最大段数为 3，(()())(())的最大段数为 2。 特别的，如果S(x,y)本身并不是合法括号序，则 f(x,y)=0。 m 次询问，每次输入一个 k，查询有多少点对的 f 值为 k。

Format

Input

第一行一个整数n，表示节点数。 接下来n-1 行每行两个整数 x,y,描述一条边。 接下来n 行，每行一个字符(或)，其中第 i 行表示i 号节点的字符。 接下来一行一个整数 m，表示询问个数。 接下来m 行，每行一个整数 k，表示一个询问。

Output

输出共m 行，每行一个整数表示有多少对x，y 满足f(x,y)=k。

Samples

6
1 2
2 6
4 2
3 4
1 5
)
(
)
)
(
)
3
1
2
3

4
2
0

Limitation

对于10%的数据，n,m≤100 对于30%的数据，n,m≤5000 对于另30%的数据，m≤10 对于100%的数据，n,m≤50000