AT_KeioPC2025_c Addictive Addition

長さ $ N $ の正整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。ここで、整数列 $ X=(X_1,X_2,\dots,X_l) $ に対して以下のように $ f(X) $ を定義します。 - $ 0 \le i \le N $ について、正整数列 $ C^{(i)} $ を $ (A_1,A_2,\dots,A_i,X_1,X_2,\dots,X_l,A_{i+1},A_{i+2},\dots,A_N,\textcolor{red}{\boldsymbol{i}}) $ と定義する。これら $ N+1 $ 個の数列のうち、辞書順で最も小さいもの(一意に定まることが証明できます)を $ C^{(k)} $ としたとき、 $ f(X) = k $ とする。 $ i = 0,1,\dots,N $ に対して、以下の問題を解いてください。 - 長さが $ 1 $ 以上 $ M $ 以下かつすべての要素が $ 1 $ 以上 $ K $ 以下であるような整数列 $ B $ のうち、 $ f(B) = i $ を満たすものの個数を $ 998244353 $ で割ったあまりを求めよ。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。 数列の辞書順とは？ 数列 \\(S = (S\_1,S\_2,\\ldots,S\_{|S|})\\) が数列 \\(T = (T\_1,T\_2,\\ldots,T\_{|T|})\\) より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、 $ |S|,|T| $ はそれぞれ \\(S, T\\) の長さを表します。 1. \\(|S| < |T|\\) かつ \\((S\_1,S\_2,\\ldots,S\_{|S|}) = (T\_1,T\_2,\\ldots,T\_{|S|})\\)。 2. ある整数 \\(1 \\le i \\le \\min\\{|S|,|T|\\}\\) が存在して、下記の $ 2 $ つがともに成り立つ。 - \\((S\_1,S\_2,\\ldots,S\_{i-1}) = (T\_1,T\_2,\\ldots,T\_{i-1})\\) - \\(S\_i\\) が \\(T\_i\\) より（数として）小さい。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ K $ $ A_1\ A_2\ \dots\ A_N $

$ T $ 行出力せよ。 $ t $ 行目には $ \mathrm{case}_t $ について、 $ i = 0,1,\dots,N $ に対する答えをこの順で空白区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、長さが $ 1 $ かつ要素が $ 1 $ 以上 $ 3 $ 以下な正整数列 $ B $ すべてについて $ C^{(i)} $ を列挙すると以下のようになります。 - $ B=(1) $ のとき、 $ C^{(0)}=(1,2,3,0),C^{(1)}=(2,1,3,1),C^{(2)}=(2,3,1,2) $ となり、 $ f(B) = 0 $ である。 - $ B=(2) $ のとき、 $ C^{(0)}=(2,2,3,0),C^{(1)}=(2,2,3,1),C^{(2)}=(2,3,2,2) $ となり、 $ f(B) = 0 $ である。 - $ B=(3) $ のとき、 $ C^{(0)}=(3,2,3,0),C^{(1)}=(2,3,3,1),C^{(2)}=(2,3,3,2) $ となり、 $ f(B) = 1 $ である。 よって、 $ i=0,1,2 $ に対する答えはそれぞれ $ 2,1,0 $ となります。 ### Constraints - $ 1 \le T \le 5 \times 10^5 $ - $ 1 \le N \le 5 \times 10^5 $ - $ 1 \le M \le 10^9 $ - $ 1 \le K \le 10^9 $ - $ 1 \le A_i \le K $ - すべてのテストケースに対する $ N $ の総和は $ 5 \times 10^5 $ 以下 - 入力はすべて整数