Migrated from Lutece 2963 Count Reachable Pairs!

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is an undirected graph with $n$ vertices and $m$ edges. The vertices are numbered from 1 to $n$, and the edges are numbered from 1 to $m$. The $i$-th edge connects vertices $u_i$ and $v_i$, and has a integer weight $w_i$. Also, You are given an integer $k$ and $q$ queries. In the $i$-th query, you are given an integer $p_i$, and you should find the number of integer pairs $(u,v)$ that satisfy the following conditions:

1. $1\le u < v \le n$;
2. It is possible to move from vertice $u$ to vertice $v$ only by using edges $j$ that satisfy $w_j \bigoplus p_i < k$. The operation $\bigoplus$ means the bitwise XOR operation.

Input

In the first line, there are three integers $n,m,k$---denoting the graph has $n$ verticles and $m$ edges, and the given integer is k. In the following $m$ lines, the $i$-th line contains three integers $u_i,v_i,w_i$---denoting the $i$-th edge connects verticles $u_i$ and $v_i$, and has a integer weight $w_i$. In the next line, there is a integer $q$, denoting the number of queries. In the following $q$ lines, the $i$-th line contains a integer $p_i$, descibing the $i$-th query.

Output

For each query print one integer in a line--- the answer for this query.

Samples

10 12 5
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
9 10 11
1 7 2
5 8 1
3 9 5
4 5 3
7
5
2
0
1
3
1
4

21
6
9
13
9
13
15

Constraints

$2\le n\le 10^5$ $1\le m,q\le 10^5$ $0\le p_i,w_j,k<2^{30}(1\le i\le q,1\le j\le m)$