問題文

長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) と Q 個のクエリが与えられます。i 個目のクエリは以下のような内容です。

• A_{x_i} を y_i に変更し、その後の A について以下の問題の答えを求める。

白い箱と黒い箱と 1 から M の番号が付いた M 個のボールがあります。始め、全てのボールは白い箱に入っています。

ここで、あなたは以下の操作を N 回繰り返します。

• 1 \le x \le M を満たす整数 x を選ぶ。ボール x を今入っている箱からもう一方の箱に移動させる。

i 回目の操作終了後、黒い箱に入っているボールの番号は全て A_i 以下である必要があります。操作列としてあり得るものの個数を 998244353 で割ったあまりを求めてください。

クエリを順に処理してください。

制約

• 1 \le N,Q \le \textcolor{red}{3 \times 10^4}
• 1 \le M \le 15
• 1 \le x_i \le N
• 1 \le A_i,y_i \le M

部分点

この問題には複数の部分点が設定されている。

• N \le 2000,M \le 10,Q = 1 を満たすデータセットに正解した場合 10 点が与えられる。
• Q = 1 を満たすデータセットに正解した場合追加で 10 点が与えられる。

入力例 1

3 3 2
1 3 1
3 2
1 3

出力例 1

5
14

1 番目のクエリの際、A=(1,3,2) となっています。このとき、操作列としては例えば以下のようなものが考えられます。

• x = 1 とする。白い箱から黒い箱にボール 1 が移動する。黒い箱の中にはボール 1 が入っている。
• x = 3 とする。白い箱から黒い箱にボール 3 が移動する。黒い箱の中にはボール 1,3 が入っている。
• x = 3 とする。黒い箱から白い箱にボール 1 が移動する。黒い箱の中にはボール 1 が入っている。

このほかに x の列として考えられるものは (1,1,1),(1,1,2),(1,2,1),(1,2,2) の 4 通りです。よって操作列としてあり得るのは 5 通りです。

入力例 2

6 8 1
3 8 7 7 1 6
1 4

出力例 2

2100

入力例 3

12 10 8
1 3 2 6 3 6 7 7 5 5 4 7
12 4
7 10
4 2
9 8
9 9
8 3
4 9
10 2

出力例 3

2741280
3007680
1503840
1916160
1972800
728640
1821600
621440