AT_oupc2023_day1_e Han Burger 2

$ N $ 個の文字あるいは文字列 $ X_1, X_2, \dots, X_N $ をこの順に連結させた文字列を $ X_1 + X_2 + \cdots + X_N $ と表記します。 また、文字列 $ X $ の $ i $ 文字目から $ j $ 文字目までを取り出した連続部分文字列を $ X[i,j] $ と表記します。 文字列に対して、バーガー、全バーガー、半バーガーを以下のように定義します。**この定義はD問題と同じです。** - バーガーとは、全バーガーである文字列、および半バーガーである文字列 - 全バーガーとは、あるバーガー $ A $ とある文字 $ c $ に対して、 $ c + A + c $ と書ける文字列、および空文字列 - 半バーガーとは、ある空でないバーガー $ A $ 、 $ B $ に対して、 $ A + B $ と書ける文字列のうち、全バーガーでない文字列 例えば、`abba` や `abbcca` は全バーガー、`aabb` や `abbacc` は半バーガーですが、`abbcbbc` や `ababa` はバーガーではありません。 英小文字からなる文字列 $ S $ と 正の整数 $ K $ が与えられます。 $ k = 0, 1, 2, \dots, K $ について、以下の問に答えてください。 - $ S[i, j] + T $ が全バーガーとなる、英小文字からなる文字列 $ T $ として考えられる長さの最小値が $ k $ となる $ (i, j) $ ( $ 1 \leq i \leq j \leq |S| $ ) の個数を $ 998244353 $ で割った余りを求めよ。

入力は以下の形式で標準入力から与えられます。 > $ S $ $ K $

$ K+1 $ 行出力してください。 $ i $ 行目に $ k = i-1 $ としたときの答えを出力してください。

### 小課題 1. ( $ 1 $ 点) $ K \leq 300 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 $ S[i,j] + T $ が全バーガーとなる $ T $ について、 $ T $ の長さの最小値が $ k $ ( $ 0 \leq k \leq 3 $ ) となる $ (i, j) $ の組はそれぞれ以下になります。 - $ k = 0 $ のとき、 $ (3, 4) $ - $ k = 1 $ のとき、 $ (1, 1), (2, 2), (3, 3), (4, 4), (2, 4) $ - $ k = 2 $ のとき、 $ (1, 2), (2, 3), (1, 4) $ - $ k = 3 $ のとき、 $ (1, 3) $ $ S[1, 4] = $ `abcc` は、 $ T = $ `ba` とすると全バーガーになります。 $ T $ の長さが $ 1 $ 以下のときは全バーガーにはなりません。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 2 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 1 \leq |S| \leq 200{,}000 $ - $ 1 \leq K \leq 200{,}000 $ - $ S $ は英小文字からなる文字列 - $ K $ は整数