Odd-Edge XOR Paths

You are given an undirected connected graph with (n) vertices and (m) edges. The (i)-th edge connects vertices (s_i) and (t_i) with weight (w_i). Note that the graph may have multiple edges and self-loops.\n\nA pair of vertices ((u, v)) (where (u) may equal (v); and if (u \neq v), ((u,v)) and ((v,u)) are considered different) is called clever with respect to (x) if there exists a path from (u) to (v) such that the XOR sum of the weights of the edges that appear an odd number of times on that path is equal to (x) (all operations in (\oplus) are on nonnegative integers).\n\nHint: In any path, edges traversed an even number of times cancel out in the XOR sum. Hence, you only care about the parity of the number of traversals. You may pick an arbitrary spanning tree and define for every vertex (i) a value (A[i]) which is the XOR sum of the weights along the tree path from a fixed source (say, vertex 1) to (i). For any path from (u) to (v), its XOR value can be written as (A[u] \oplus A[v] \oplus r), where (r) is an element from the cycle space (i.e. an XOR combination of cycles). Thus, the condition is equivalent to the existence of some (r) (belonging to the vector space spanned by the XOR values of the cycles) such that (A[u] \oplus A[v] \oplus r = x). This in turn is equivalent to (A[u] \oplus A[v] \equiv x \pmod{S}) where (S) is the subspace of (\mathbb{Z}_2) formed by all possible values (r).\n\nThe problem asks you to answer (q) queries. In each query, given an integer (x), determine how many ordered pairs ((u,v)) are clever with respect to (x).

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of vertices and edges.

The next \(m\) lines each contain three integers \(s_i\), \(t_i\) and \(w_i\) representing an edge between \(s_i\) and \(t_i\) with weight \(w_i\).

The next line contains an integer \(q\) — the number of queries.

The following \(q\) lines each contain a single integer \(x\).

outputFormat

For each query, output a single line containing the number of ordered pairs \((u,v)\) that are clever with respect to \(x\).

sample

2 1
1 2 3
2
3
0

2
2