問題文

$(N+1)$ 頂点の有向グラフ $D$ がある. $D$ における $(N+1)$ 個の頂点は頂点 $0,1,2, \dots, N$ と名付けられている.

$0 \leq u \leq N, 0 \leq v \leq N$ に対して, 頂点 $u$ から頂点 $v$ を結ぶ有向辺が $X_{u,v}$ 本ある. ここで, $u \geq v$ ならば, $X_{u,v}=0$ である.

この $D$ について, 以下の $Q$ 個の質問, 質問 $1$, $\cdots$, 質問 $Q$ に答えよ.

• 質問 $q$ : $D$ に対して, 以下の操作を $k=1,2, \dots, K_q$ の順に行って得られる有向グラフを $D'$ とする.
  • 頂点 $A_{q,k}$ から頂点 $B_{q,k}$ へ結ぶ有向辺を $C_{q,k}$ 本追加する. ここで, $A_{q,k} \lt B_{q,k}$ である.
  このとき, $D'$ において, 頂点 $0$ から頂点 $N$ へのパスの数を $998244353$ で割った余りを求めよ. なお, 条件を満たすパスの数は有限であることが証明できる.

ただし, たどった頂点が同じでも, 辺が異なっている部分があればそれらは異なるパスとする.

なお, 各質問は独立した問題とせよ. つまり, 質問 $q$ で追加された有向辺が別の質問における $D$ に追加されることはない.

制約

• $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)$.
• 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.

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

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行には質問 $q$ に対する解答を整数で出力せよ.

最後に改行を忘れないこと.

また, この問題では入力が大量になる場合があるので, 高速な入力を利用することをおすすめする.

サンプル

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