Kelian Ji is a girl who loves creating "simple" problems. As the name suggests, a "simple" problem is one that contains many "simples" in its description.
Kelian first provides a simple connected undirected graph, where each edge has a positive integer weight. Specifically, Kelian guarantees that the sum of edge weights for any two simple cycles in the graph is equal.
Later, Kelian wants to hide the beautiful properties of the graph, so she changes the weights of some edges to new values. Consequently, the original beautiful properties may no longer exist after the modification.
Now, she provides the modified graph along with multiple queries. Each query asks for the sum of weights of all simple paths between two points $S$ and $T$. Since the answer can be very large, you only need to output the result modulo $998\,244\,353$.
Specifically, a simple graph contains no multiple edges or self-loops, and a simple cycle or simple path does not contain repeated nodes.
Input
The first line contains three integers $n, m, q$.
The next $m$ lines each contain three integers $u, v, w$, representing an undirected edge $(u, v)$ with weight $w$.
The next $q$ lines each contain two integers $S, T$ for each query.
Output
For each query, output a single integer representing the result modulo $998\,244\,353$.
Constraints
For all test cases, $1 \le n, q \le 500\,000$, $n - 1 \le m \le 640\,000$, $1 \le u, v, S, T \le n$, $1 \le w \le 10^6$. The graph has no multiple edges or self-loops and is connected.
The specific constraints for each test case are as follows:
| Test Case ID | Special Constraint 1 | Special Constraint 2 |
|---|---|---|
| 1 | $m < n$ | Guaranteed existence of a simple path passing through all nodes |
| 2 | $m < n$ | None |
| 3 $\sim$ 5 | No node is on $\ge 2$ simple cycles | Guaranteed existence of a simple path passing through all nodes |
| 6 $\sim$ 8 | No node is on $\ge 2$ simple cycles | None |
| 9 $\sim$ 14 | None | Guaranteed existence of a simple path passing through all nodes |
| 15 $\sim$ 20 | None | None |
Examples
Input 1
(See the provided files simple_ex1.in and simple_ex2.in)
Output 1
(See the provided files simple_ex1.ans and simple_ex2.ans)