题目描述

一场盛大的魔术表演即将举行。这座城市里有 $n$ 个舞台，它们通过一套秘密通道相连。每个舞台对应一个顶点，每条连接两个舞台的通道对应一条边。通道共有 $n-1$ 条，构成一棵树。

每条边上都写着一个数 $w$，表示观众通过这条通道从一个舞台来到另一个舞台时所感受到的“幻象之力”。

考虑表演中的任意一条路线：它是由互不相同的舞台组成的序列 $u_1,u_2,\ldots,u_k$，其中 $k\ge 2$，且每两个相邻舞台之间都有一条直接相连的秘密通道。这条路线不能自相交，也就是说，同一个舞台不能出现两次。

将路线的美丽值定义为这条路径上所有幻象之力的按位异或：

$$w_{u_1\rightarrow u_2}\oplus w_{u_2\rightarrow u_3}\oplus\cdots\oplus w_{u_{k-1}\rightarrow u_k}.$$

一条路线与它的反向路线视为同一条路线。表演的组织者想知道，美丽值等于指定值的不同路线共有多少条。

输入格式

第一行包含整数 $n$，表示舞台的数量，满足 $2\le n\le 2\cdot 10^5$。

接下来 $n-1$ 行描述秘密通道。每行包含三个整数 $u,v,w$，分别表示通道两端的舞台编号和该通道上的幻象之力，满足 $1\le u,v\le n$、$0\le w<2^{20}$。

接下来一行包含询问数量 $q$，满足 $1\le q\le 2\cdot 10^5$。

接下来 $q$ 行，每行包含一个整数 $f$，表示要求的路线美丽值，满足 $0\le f<2^{20}$。

保证给出的图是一棵树。

输出格式

对于每个询问，单独输出一行一个整数：舞台对之间美丽值等于指定 $f$ 的不同路线数量。

3
1 2 0
2 3 1
3
0
1
2

1
2
0

3
1 2 10
2 3 5
3
0
5
15

0
1
1