Background

xtq started studying discrete mathematics a lot when he was in sixth grade. One day, he was thinking while looking at a very dense graph.

Problem Description

xtq has an undirected connected graph with $n$ vertices and $m$ edges. The $i$-th edge connects $s_i$ and $t_i$ and has weight $w_i$. Multiple edges and self-loops are not guaranteed to be absent.

xtq thinks that if there exists a path starting from $u$ and ending at $v$ such that the XOR sum of the weights of all edges that are traversed an odd number of times by this path equals $x$, then the ordered pair $(u,v)$ is “clever” with respect to $x$.

Now, xtq asks you $q$ queries. For each query, ask how many distinct ordered pairs $(u,v)$ are clever with respect to $x$. Note that $u$ may equal $v$, and if $u \neq v$, then $(u,v)$ and $(v,u)$ are considered different.

Input Format

The first line contains three positive integers $n,m,q$.

The next $m$ lines each contain three integers $s_i,t_i,w_i$.

The next $q$ lines each contain one integer $x$, representing a query.

Output Format

Output $q$ lines. Each line answers one query, and you should print the result modulo $998244353$.

3 3 3
1 2 0
2 3 1
3 1 2
0
1
2

5
4
4

4 3 2
1 2 1
2 3 6
2 4 7
6
7

4
4

Hint

Sample Explanation 1

Ordered pairs that are clever with respect to $0$:

$(1,1): 1 \Rightarrow 2 \Rightarrow 1$, and $(2,2),(3,3)$ are similar; $(1,2): 1 \Rightarrow 2$, and $(2,1)$ is similar.

Ordered pairs that are clever with respect to $1$:

$(2,3):2 \Rightarrow 3$, and $(3,2)$ is similar; $(1,3):1 \Rightarrow 2 \Rightarrow 3$, and $(3,1)$ is similar.

Ordered pairs that are clever with respect to $2$: similar to $1$.

Constraints

For $100\%$ of the testdata, $1\le n\le 10^5,n-1\le m\le 3*10^5,0\le w_i,x< 262144,0\le q\le 262144$.

Translated by ChatGPT 5