P17898 [ICPC 2026 Nanchang I] Legacy Code
Description
You have a piece of legacy code:
$$
\begin{array}{l}
\textbf{for } t = 1 \textbf{ to } k \textbf{ do} \\
\qquad a_{x_1} \leftarrow (a_{u_1} \times a_{v_1}) \bmod MOD \\
\qquad a_{x_2} \leftarrow (a_{u_2} \times a_{v_2}) \bmod MOD \\
\qquad a_{x_3} \leftarrow (a_{u_3} \times a_{v_3}) \bmod MOD \\
\qquad \vdots \\
\qquad a_{x_m} \leftarrow (a_{u_m} \times a_{v_m}) \bmod MOD \\
\textbf{end for}
\end{array}
$$
where $MOD = 998\,244\,353$ and $x_i, u_i, v_i \in \{1, \dots, n\}$ for $i = 1, \dots, m$.
Given the initial values of the variables $a_1, a_2, \dots, a_n$, compute their final values after the loop runs $k$ times. You need to answer $q$ such queries.
Input Format
The first line contains three integers $n$, $m$ and $q$ ($1 \leq n \leq 200$, $1 \leq m \leq 2 \times 10^5$, $1 \leq q \leq 200$).
The next $m$ lines each contain three integers $x_i$, $u_i$, $v_i$ ($1 \leq x_i, u_i, v_i \leq n$).
Each of the next $q$ lines represents a query. Each query contains $n+1$ integers:
- the number of iterations $k$ ($1 \le k \le 10^6$),
- the initial values of the $n$ variables $a_1, a_2, \dots, a_n$ ($0 \le a_i < 998\,244\,353$).
Output Format
For each query, output a single line containing $n$ integers --- the final values of $a_1, a_2, \dots, a_n$ after executing the code, each modulo $998\,244\,353$.