AT_npcapc_2024_d Two Box

長さ $ 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 $ で割ったあまりを求めてください。 クエリを順に処理してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_Q $ $ y_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 個目のクエリの答えを出力せよ。

### 部分点 この問題には複数の部分点が設定されている。 - $ N \le 2000,M \le 10,Q = 1 $ を満たすデータセットに正解した場合 $ 10 $ 点が与えられる。 - $ Q = 1 $ を満たすデータセットに正解した場合追加で $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ 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 $ 通りです。 ### Constraints - $ 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 $