P5169 xtq’s XOR Sum

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.

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.

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 $q$ lines. Each line answers one query, and you should print the result modulo $998244353$.

### 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 | Test Point ID |$n$ |$m$ | $\, w_i,x,q-1$ | Special Restriction | | ----------- | ----------- | ----------- | --------------- | ----------- | |$1$ |$\le 5$ |$\le 10$ |$< 4$ | None | |$2$ |$\le 10$ |$\le 50$ |$< 8$ | ^ | |$3$ |$\le 100$ |$= n-1$ |$< 128$ | A tree | |$4$ |^ |$\le 500$ |^ | None | |$5$ |$\le 1000$ |$= n-1$ |$< 1024$ | A tree | |$6$ |^ |$\le 5000$ |^ | None | |$7$ |$\le 1 \times 10^5 $ |$\le 3\times 10^5$ |^ | ^ | |$8$ |^|^ |^| ^ | |$9$ |^|$= n-1$ |$< 262144$ | A tree | |$10$ |^|^ |^| ^ | |$11$ |^|^ |^ | ^ | |$12$ |^|^|^ | ^ | |$13$ |^|$\le n+11$ |^| None | |$14$ |^|^ |^ | ^ | |$15$ |^|$\le 3\times 10^5$ |^ | ^ | |$16$ |^|^ |^ | ^ | |$17$ |^|^ |^| ^ | |$18$ |^|^|^| ^ | |$19$ |^|^|^| ^ | |$20$ |^|^ |^ | ^ | 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