K. Legacy Code
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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 \lt 998\,244\,353$$$).
Output

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$$$.

Example
Input
7 8 4
3 1 2
4 3 3
5 6 7
7 1 3
2 2 2
6 6 2
1 5 6
7 7 7
1 2 1 1 1 1 1 1
2 1 2 3 4 5 6 7
3 1 1 0 1 0 1 0
100 11 45 14 19 19 8 10
Output
1 1 2 4 1 1 16
36864 16 4032 16257024 96 384 227524445
0 1 1 1 0 1 1
244858606 337827833 584144609 343808937 412777304 279017446 926699892