Problem Statement

There is a directed graph $D$ with $(N+1)$ vertices. The $(N+1)$ vertices of $D$ are named vertices $0,1,2, \dots, N$.

For $0 \leq u \leq N, 0 \leq v \leq N$, there are $X_{u,v}$ directed edges from vertex $u$ to vertex $v$. Here, if $u \geq v$, then $X_{u,v}=0$.

For this $D$, answer the following $Q$ questions, Question $1$, $\cdots$, Question $Q$.

• Question $q$ : Let $D'$ be the directed graph obtained by performing the following operation on $D$ in the order $k=1,2, \dots, K_q$.
  • Add $C_{q,k}$ directed edges from vertex $A_{q,k}$ to vertex $B_{q,k}$. Here, $A_{q,k} \lt B_{q,k}$.
  Find the number of paths from vertex $0$ to vertex $N$ in $D'$, modulo $998244353$. It can be proved that the number of paths satisfying the condition is finite.

Here, even if the visited vertices are the same, two paths are considered different if they differ in any of their edges.

Note that each question is an independent problem. That is, directed edges added in Question $q$ are not added to $D$ in any other question.

Constraints

• $1 \leq N \leq 400$.
• $0 \leq X_{u,v} \leq 998244353 \quad (0 \leq u \leq N, 0 \leq v \leq N)$.
• $u \geq v \Rightarrow X_{u,v}=0 \quad (0 \leq u \leq N, 0 \leq v \leq N)$.
• $1 \leq Q \leq 3 \times 10^4$.
• $1 \leq K_q \leq 30 \quad (1 \leq q \leq Q)$.
• $0 \leq A_{q,k} \lt B_{q,k} \leq N \quad (1 \leq q \leq Q, 1 \leq k \leq K_q)$.
• $1 \leq C_{q,k} \leq 998244353 \quad (1 \leq q \leq Q, 1 \leq k \leq K_q)$.
• All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$X_{0,0}$ $X_{0,1}$ $\cdots$ $X_{0,N}$
$X_{1,0}$ $X_{1,1}$ $\cdots$ $X_{1,N}$
$\vdots$
$X_{N,0}$ $X_{N,1}$ $\cdots$ $X_{N,N}$
$Q$
$\textrm{Question}_1$
$\textrm{Question}_2$
$\vdots$
$\textrm{Question}_Q$

$K_q$
$A_{q,1}$ $B_{q,1}$ $C_{q,1}$
$A_{q,2}$ $B_{q,2}$ $C_{q,2}$
$\vdots$
$A_{q,K_q}$ $B_{q,K_q}$ $C_{q,K_q}$

Output

The output consists of $Q$ lines. On line $q~(1 \leq q \leq Q)$, print the answer to Question $q$ as an integer.

Do not forget the newline at the end.

Also, since the input can be large in this problem, using fast input is recommended.

Sample

4
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
1
2
0 4 1
1 4 2

4

2
0 0 0
0 0 0 
0 0 0
2
1
0 1 100
3
0 1 100
1 2 100
0 1 100

0
20000

6
0 314159265 358979323 846264338 327950288 41971693 993751058
0 0 271828182 845904523 536028747 135266249 775724709
0 0 0 161803398 874989484 820458683 436563811
0 0 0 0 141421356 237309504 880168872
0 0 0 0 0 207879576 350761908
0 0 0 0 0 0 123456789
0 0 0 0 0 0 0
1
4
1 4 46
3 5 4646
2 5 464646
3 4 46464646

368653717