AT_aalc001_g k 乗和

長さ $ N $ の非負整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 クエリを $ Q $ 個処理してください。クエリは以下の $ 2 $ 種類のいずれかです。 - `1 l r x`： $ i=l,l+1,\ldots,r $ のそれぞれについて、 $ A_i $ に $ x $ を加える。 - `2 l r k`： $ \displaystyle \sum_{i=l}^{r} A_i^k $ を $ 998244353 $ で割った余りを出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下のいずれかの形式で与えられる。 > $ 1 $ $ l $ $ r $ $ x $ > $ 2 $ $ l $ $ r $ $ k $

$ 2 $ 種類目のクエリの個数を $ q $ として、 $ q $ 行出力せよ。 $ j $ 行目には、 $ j $ 番目の $ 2 $ 種類目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、 $ 1+2+3+4=10 $ を出力します。 $ 3 $ 番目のクエリによって $ A=(1,7,8,4) $ となります。したがって、 $ 4 $ 番目のクエリでは $ 1^3+7^3+8^3=856 $ を出力します。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 10^9 $ - $ 1 $ 種類目のクエリについて、 $ 1 \leq l \leq r \leq N $ , $ 0 \leq x \leq 10^9 $ - $ 2 $ 種類目のクエリについて、 $ 1 \leq l \leq r \leq N $ , $ 1 \leq k \leq 4 $ - 入力される数値はすべて整数