Cho một cây gồm ~n~ đỉnh (đánh số từ ~1~ đến ~n~). Mỗi cạnh có trọng số ~w~.

Xét một đường đi đơn (không lặp đỉnh) bất kỳ gồm các đỉnh phân biệt ~u_1, u_2, \dots, u_k~ với ~k \ge 2~, trong đó mỗi cặp liên tiếp ~(u_i, u_{i+1})~ được nối bởi một cạnh của cây.

Vẻ đẹp của đường đi được định nghĩa là XOR của các trọng số trên đường đi:

~w_{(u_1,u_2)} \mathbin{\oplus} w_{(u_2,u_3)} \mathbin{\oplus} \dots \mathbin{\oplus} w_{(u_{k-1},u_k)}~.

Bạn được cho ~q~ truy vấn, mỗi truy vấn là một giá trị ~f~. Với mỗi ~f~, hãy đếm số lượng đường đi (tương ứng với các cặp đỉnh không kể thứ tự) có vẻ đẹp đúng bằng ~f~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(2 \le n \le 2 \cdot 10^5)~;

• ~n-1~ dòng tiếp theo, mỗi dòng gồm ba số ~u, v, w~ ~(0 \le w < 2^{20})~ — một cạnh nối ~u~ và ~v~ với trọng số ~w~;

• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 2 \cdot 10^5)~;

• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~f~ ~(0 \le f < 2^{20})~.

Output

In ra ~q~ dòng, dòng thứ ~i~ là số lượng đường đi có vẻ đẹp bằng ~f_i~.

Scoring

Sample Input 1

3
1 2 0
2 3 1
3
0
1
2

Sample Output 1

1
2
0

Sample Input 2

3
1 2 10
2 3 5
3
0
5
15

Sample Output 2

0
1
1

Notes

Trong ví dụ 1:

• Đường đi giữa cặp đỉnh ~(1,2)~ có vẻ đẹp bằng ~0~;

• Đường đi giữa cặp đỉnh ~(1,3)~ có vẻ đẹp bằng ~1~;

• Đường đi giữa cặp đỉnh ~(2,3)~ có vẻ đẹp bằng ~1~.

Trong ví dụ 2:

• Đường đi giữa cặp đỉnh ~(1,2)~ có vẻ đẹp bằng ~10~;

• Đường đi giữa cặp đỉnh ~(1,3)~ có vẻ đẹp bằng ~15~;

• Đường đi giữa cặp đỉnh ~(2,3)~ có vẻ đẹp bằng ~5~.