AT_abc418_f [ABC418F] We're teapots

$ N $ 個のティーポットが横一列に並んでおり、左から順に $ 1 $ から $ N $ までの番号が付けられています。 整数列 $ (a_1, \dots, a_N) $ があり、はじめその値は $ a_1 = \dots = a_N = -1 $ です。 あなたは以下の条件をすべて満たすように、それぞれのティーポットに紅茶かコーヒーのいずれか $ 1 $ つを入れます。 - どの隣り合う $ 2 $ つのティーポットについても、少なくとも片方には紅茶を入れる。 - $ 1 \leq i \leq N $ を満たす整数 $ i $ について、 $ a_i \neq -1 $ である場合、ティーポット $ 1, \dots, i $ のうちちょうど $ a_i $ 個にコーヒーを入れる。 クエリが $ Q $ 個与えられるので、与えられた順に処理してください。 $ j $ 番目のクエリ ( $ 1 \leq j \leq Q $ ) は以下の通りです。 - $ a_{X_j} $ の値を $ Y_j $ に変更する。その後、条件を満たすようなティーポットの満たし方の個数を $ 998244353 $ で割ったあまりを出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 $ j $ 行目 ( $ 1 \leq j \leq Q $ ) には、 $ j $ 番目のクエリで出力するべき値を出力せよ。

### Sample Explanation 1 - $ 1 $ 番目のクエリでの操作後、 $ a = (1,\ -1,\ -1,\ -1,\ -1) $ となります。条件を満たす入れ方は以下の $ 5 $ 通りです。 - ティーポット $ 1 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 1, 3 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 1, 3, 5 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 1, 4 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 1, 5 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - $ 2 $ 番目のクエリでの操作後、 $ a = (1,\ -1,\ -1,\ 2,\ -1) $ となります。条件を満たす入れ方は以下の $ 3 $ 通りです。 - ティーポット $ 1, 3 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 1, 3, 5 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 1, 4 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - $ 3 $ 番目のクエリでの操作後、 $ a = (0,\ -1,\ -1,\ 2,\ -1) $ となります。条件を満たす入れ方は以下の $ 1 $ 通りです。 - ティーポット $ 2, 4 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - $ 4 $ 番目のクエリでの操作後、 $ a = (0,\ -1,\ -1,\ -1,\ -1) $ となります。条件を満たす入れ方は以下の $ 8 $ 通りです。 - どのティーポットにもコーヒーを入れず、すべてのティーポットに紅茶を入れる。 - ティーポット $ 2 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 2, 4 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 2, 5 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 3 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 3, 5 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 4 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 5 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - $ 5 $ 番目のクエリでの操作後、 $ a = (0,\ -1,\ -1,\ -1,\ 1) $ となります。条件を満たす入れ方は以下の $ 4 $ 通りです。 - ティーポット $ 2 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 3 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 4 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - ティーポット $ 5 $ にコーヒーを入れ、ほかのティーポットに紅茶を入れる。 - $ 6 $ 番目のクエリでの操作後、 $ a = (0,\ -1,\ -1,\ -1,\ 5) $ となります。条件を満たす入れ方は $ 0 $ 通りです。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq X_j \leq N $ ( $ 1 \leq j \leq Q $ ) - $ -1 \leq Y_j \leq X_j $ ( $ 1 \leq j \leq Q $ ) - 入力される値は全て整数である。