题目描述
Problem Background
xtq began extensively studying discrete mathematics in the sixth grade. One day, he was pondering over a densely packed graph.
Problem Description
xtq has an undirected connected graph with \( n \) vertices and \( m \) edges. The \( i \)-th edge connects vertices \( s_i \) and \( t_i \) with a weight \( w_i \). The graph is not guaranteed to be free of multiple edges or self-loops.
xtq believes that if there exists a path from \( u \) to \( v \) such that the XOR sum of the weights of all edges traversed an odd number of times along this path equals \( x \), then the pair of vertices \( (u, v) \) is clever with respect to \( x \).
Now, xtq asks you \( q \) questions, each asking how many distinct pairs of vertices \( (u, v) \) are clever with respect to \( x \). Note that \( u \) can be equal to \( 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 \), and \( q \).
The next \( m \) lines each contain three integers \( s_i \), \( t_i \), and \( w_i \).
The next \( q \) lines each contain one integer \( x \), representing a query.
Output Format
Output \( q \) lines, each answering a query by outputting the result modulo 998244353.
Sample Input and Output
Input Sample #1
3 3 3
1 2 0
2 3 1
3 1 2
0
1
2
Output Sample #1
5
4
4
Input Sample #2
4 3 2
1 2 1
2 3 6
2 4 7
6
7
Output Sample #2
4
4
Notes
Sample Explanation 1
Clever pairs with respect to \( 0 \):
\( (1,1): 1 \Rightarrow 2 \Rightarrow 1 \), \( (2,2) \), \( (3,3) \) similarly; \( (1,2): 1 \Rightarrow 2 \), \( (2,1) \) similarly
Clever pairs with respect to \( 1 \):
\( (2,3): 2 \Rightarrow 3 \), \( (3,2) \) similarly; \( (1,3): 1 \Rightarrow 2 \Rightarrow 3 \), \( (3,1) \) similarly
Clever pairs with respect to \( 2 \): Similar to \( 1 \)
Data Range
| Test Point Number | \( n \) | \( m \) | \( w_i, x, q-1 \) | Special Constraints |
|---|---|---|---|---|
| 1 | \(\le 5\) | \(\le 10\) | \(< 4\) | None |
| 2 | \(\le 10\) | \(\le 50\) | \(< 8\) | None |
| 3 | \(\le 100\) | \(= n-1\) | \(< 128\) | Tree |
| 4 | \(\le 100\) | \(\le 500\) | \(< 128\) | None |
| 5 | \(\le 1000\) | \(= n-1\) | \(< 1024\) | Tree |
| 6 | \(\le 1000\) | \(\le 5000\) | \(< 1024\) | None |
| 7 | \(\le 100000\) | \(\le 300000\) | \(< 1024\) | None |
| 8 | \(\le 100000\) | \(\le 300000\) | \(< 1024\) | None |
| 9 | \(\le 100000\) | \(= n-1\) | \(< 262144\) | Tree |
| 10 | \(\le 100000\) | \(= n-1\) | \(< 262144\) | Tree |
| 11 | \(\le 100000\) | \(= n-1\) | \(< 262144\) | Tree |
| 12 | \(\le 100000\) | \(= n-1\) | \(< 262144\) | Tree |
| 13 | \(\le 100000\) | \(\le n+11\) | \(< 262144\) | None |
| 14 | \(\le 100000\) | \(\le n+11\) | \(< 262144\) | None |
| 15 | \(\le 100000\) | \(\le 300000\) | \(< 262144\) | None |
| 16 | \(\le 100000\) | \(\le 300000\) | \(< 262144\) | None |
| 17 | \(\le 100000\) | \(\le 300000\) | \(< 262144\) | None |
| 18 | \(\le 100000\) | \(\le 300000\) | \(< 262144\) | None |
| 19 | \(\le 100000\) | \(\le 300000\) | \(< 262144\) | None |
| 20 | \(\le 100000\) | \(\le 300000\) | \(< 262144\) | None |
For 100% of the data, \( 1 \le n \le 10^5 \), \( n-1 \le m \le 3 \times 10^5 \), \( 0 \le w_i, x < 262144 \), \( 0 \le q \le 262144 \).
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分