xtq的异或和
题目背景
xtq在六年级的时候开始大量研究离散数学。这一天,他正在对着一张密密麻麻的图思索。
题目描述
xtq有一张$n$个点,$m$条边的无向连通图。第$i$条边连接$s_i,t_i$,权值为$w_i$。不保证无重边或自环。
xtq认为,如果存在一条从$u$出发,到$v$结束的路径,使得所有**被这条路径恰经过奇数次的边**的权值的异或和为$x$,那么点对$(u,v)$关于$x$是巧妙的。
现在,xtq问了你$q$个问题,每次询问有多少个不同的点对$(u,v)$关于$x$是巧妙的。注意$u$可以等于$v$,且如果$u \neq v$那么$(u,v)$与$(v,u)$是不同的。
输入输出格式
输入格式
第一行,三个正整数$n,m,q$
接下来$m$行,每行三个整数$s_i,t_i,w_i$
接下来$q$行,每行一个整数$x$,表示一次询问。
输出格式
$q$行,每行回答一次询问,输出对998244353取模后的结果。
输入输出样例
输入样例 #1
3 3 3
1 2 0
2 3 1
3 1 2
0
1
2
输出样例 #1
5
4
4
输入样例 #2
4 3 2
1 2 1
2 3 6
2 4 7
6
7
输出样例 #2
4
4
说明
##样例解释1
关于$0$巧妙的点对:
$(1,1): 1 \Rightarrow 2 \Rightarrow 1$,$(2,2),(3,3)$类似;$(1,2): 1 \Rightarrow 2$,$(2,1)$类似
关于$1$巧妙的点对:
$(2,3):2 \Rightarrow 3$,$(3,2)$类似;$(1,3):1 \Rightarrow 2 \Rightarrow 3$,$(3,1)$类似
关于$2$巧妙的点对:与$1$类似
##数据范围
| 测试点编号|$n$ |$m$ | $\, w_i,x,q-1$ | 特殊限制 |
| ----------- | ----------- | ----------- | --------------- | ----------- |
|1 |$\le 5$ |$\le 10$ |$< 4$ | 无 |
|2 |$\le 10$ |$\le 50$ |$< 8$ | 无 |
|3 |$\le 100$ |$= n-1$ |$< 128$ | 是一棵树 |
|4 |$\le 100$ |$\le 500$ |$< 128$ | 无 |
|5 |$\le 1000$ |$= n-1$ |$< 1024$ | 是一棵树 |
|6 |$\le 1000$ |$\le 5000$ |$< 1024$ | 无 |
|7 |$\le 100000$ |$\le 300000$ |$< 1024$ | 无 |
|8 |$\le 100000$ |$\le 300000$ |$< 1024$ | 无 |
|9 |$\le 100000$ |$= n-1$ |$< 262144$ | 是一棵树 |
|10 |$\le 100000$ |$= n-1$ |$< 262144$ | 是一棵树 |
|11 |$\le 100000$ |$= n-1$ |$< 262144$ | 是一棵树 |
|12 |$\le 100000$ |$= n-1$ |$< 262144$ | 是一棵树 |
|13 |$\le 100000$ |$\le n+11$ |$< 262144$ | 无 |
|14 |$\le 100000$ |$\le n+11$ |$< 262144$ | 无 |
|15 |$\le 100000$ |$\le 300000$ |$< 262144$ | 无 |
|16 |$\le 100000$ |$\le 300000$ |$< 262144$ | 无 |
|17 |$\le 100000$ |$\le 300000$ |$< 262144$ | 无 |
|18 |$\le 100000$ |$\le 300000$ |$< 262144$ | 无 |
|19 |$\le 100000$ |$\le 300000$ |$< 262144$ | 无 |
|20 |$\le 100000$ |$\le 300000$ |$< 262144$ | 无 |
对于100%的数据,$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$