给定整数 $N, M, K$，以及一个包含 $N$ 个顶点和 $M$ 条边的无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边 ($1 \le i \le M$) 连接顶点 $A_i$ 和 $B_i$，并具有一个非负整数权值 $C_i$。图中可能存在重边，但没有自环。

给定 $Q$ 次查询。在第 $i$ 次 ($1 \le i \le Q$) 查询中，给定一个整数 $D_i$。求满足以下条件的整数对 $(u, v)$ 的数量：

• $1 \le u < v \le N$
• 仅使用满足 $(C_j \oplus D_i) < K$ 的边 $j$，即可从顶点 $u$ 到达顶点 $v$，其中 $\oplus$ 表示按位异或运算。

输入格式

输入通过标准输入给出，格式如下：

$N \ M \ K$ $A_1 \ B_1 \ C_1$ $A_2 \ B_2 \ C_2$ $\vdots$ $A_M \ B_M \ C_M$ $Q$ $D_1$ $D_2$ $\vdots$ $D_Q$

• 输入中的所有值均为整数。
• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $0 \le K < 2^{30}$
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$)
• $0 \le C_i < 2^{30}$ ($1 \le i \le M$)
• $1 \le Q \le 10^5$
• $0 \le D_i < 2^{30}$ ($1 \le i \le Q$)

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 次查询的答案。

样例

样例输入 1

4 5 5
1 2 17
1 3 4
2 3 20
2 4 3
3 4 5
4
0
7
16
167

样例输出 1

2
6
3
0

样例输入 2

9 13 488888932
2 7 771479959
3 8 783850182
5 7 430673756
6 8 350738034
4 9 400768807
2 3 83653266
1 2 829786563
5 8 357613791
7 9 579696618
3 7 423191200
3 5 867380255
1 9 907715012
6 9 1033650694
8
498260055
144262908
117665696
848664012
983408133
32610599
478007408
134182829

样例输出 2

16
7
5
13
13
16
16
5