AT_arc218_e [ARC218E] Reverse and Reverse

$ (1,2,\dots,N) $ の順列 $ p=(p_1,p_2,\dots,p_N) $ と正整数 $ M $ に対して、以下の問題の答えを $ f(p,M) $ と置きます。 > $ p $ に対して以下の操作を $ M $ 回行います。 > > - $ 1 \le i \le N-1 $ を満たす整数 $ i $ を選び、 $ (p_1,p_2,\dots,p_i) $ と $ (p_{i+1},p_{i+2},\dots,p_N) $ をそれぞれ反転する。形式的には、 $ p $ を $ (p_i,p_{i-1},\dots,p_1,p_N,p_{N-1},\dots,p_{i+1}) $ に置き換える。 > > 操作列としてあり得るものは $ (N-1)^M $ 通りありますが、その全てに対する「 $ M $ 回の操作終了後の $ p $ の転倒数」の総和を $ 998244353 $ で割った余りを求めてください。 $ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ が与えられます。以下のクエリを $ Q $ 回処理してください。 - $ 1 \le x \le N-1 $ を満たす整数 $ x $ と正整数 $ K $ が与えられる。 $ P_x,P_{x+1} $ を swap する。その後、 $ f(P,K) $ を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ P_1\ P_2\ \dots\ P_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ x $ $ K $

$ Q $ 行出力せよ。 $ i $ 行目には $ \mathrm{query}_i $ の答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリについて、 $ P_1,P_2 $ を swap することで $ P=(3,1,2) $ となります。操作列は $ 2 $ 通りあり、それぞれ以下のようになります。 - $ i = 1 $ を選ぶ。 $ P=(3,2,1) $ となる。転倒数は $ 3 $ である。 - $ i = 2 $ を選ぶ。 $ P=(1,3,2) $ となる。転倒数は $ 1 $ である。 よって答えは $ 3+1=4 $ です。 $ 2 $ 番目のクエリについて、 $ P_2,P_3 $ を swap することで $ P=(3,2,1) $ となります。操作列は $ 2 $ 通りあり、それぞれ以下のようになります。 - $ i = 1 $ を選ぶ。 $ P=(3,1,2) $ となる。転倒数は $ 2 $ である。 - $ i = 2 $ を選ぶ。 $ P=(2,3,1) $ となる。転倒数は $ 2 $ である。 よって答えは $ 2+2=4 $ です。 ### Constraints - $ 2 \le N \le 2 \times 10^5 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ P $ は $ (1,2,\dots,N) $ の順列 - $ 1 \le x \le N-1 $ - $ 1 \le K \le 10^9 $ - 入力は全て整数