$n$ 個の文字列 $s_1, s_2, \dots, s_n$ が与えられます。各文字列には重み $w_i$ が割り当てられています。

$S[l:r]$ を文字列 $S$ の $l$ 文字目から $r$ 文字目までの部分文字列（添字は $1$ から開始）とし、$f(S, T)$ を文字列 $T$ が文字列 $S$ に出現する回数とします。

$g(S) = \sum_{i=1}^{n} w_i \times f(S, s_i)$ とし、$h(S) = \max_{1 \le l \le r \le |S|} \frac{g(S[l:r])}{r-l+1}$ と定義します。

$\forall h(S) = \frac{a}{b}$ （ただし $a, b$ は互いに素）に対し、$\hat{h}(S) = a \cdot b^{-1} \bmod 998244353$ と定めます。ここで $b^{-1}$ は $b$ の $\bmod 998244353$ における乗法逆元を表します。本問で遭遇するすべてのケースにおいて $b$ は乗法逆元を持つことが証明できます。

すべての $1 \le i \le n, 1 \le j \le |s_i|$ について、$h(s_i[1:j])$ を求めてください。一部のサブタスクでは答えの一部のみが要求されます。詳細は入出力形式を参照してください。

入力

1行目に2つの整数 $n, T$ が与えられます。それぞれ文字列の数とテストケースのタイプを表します。

続く $n$ 行には、文字列 $s_i$ と正の整数 $w_i$ が与えられます。

出力

$T=0$ のサブタスクについては、$h(s_1)$ を浮動小数点数として出力してください。出力結果と標準出力の絶対誤差が $10^{-4}$ 以内であれば正解とみなされます。

$T=1$ のサブタスクについては、出力量を減らすため、$\oplus_{1 \le i \le n, 1 \le j \le |s_i|} \hat{h}(s_i[1:j])$ のみを出力してください。ここで $\oplus$ はビット単位の排他的論理和（C++言語における ^ 演算子）を表します。

入出力例

入出力例 1

4 0
ababcdcd 0
ab 12
abc 20
bc 15

15.666667

入出力例 2

4 1
ababcdcd 0
ab 12
abc 20
bc 15

980069045

小課題

$m = \sum_{i=1}^{n} |s_i|, l = \max_{i=2}^{n} |s_i|$ とします。

• $\mathrm{subtask\, 1}(3\,\mathrm{pts}):$ $m, l \le 50$、$T=1$
• $\mathrm{subtask\, 2}(14\,\mathrm{pts}):$ $m, l \le 2000$、$T=1$
• $\mathrm{subtask\, 3}(19\,\mathrm{pts}):$ $m \le 10^5, l \le 50$、$T=0$
• $\mathrm{subtask\, 4}(23\,\mathrm{pts}):$ $m, l \le 10^5$、$T=0$
• $\mathrm{subtask\, 5}(15\,\mathrm{pts}):$ $m, l \le 3 \cdot 10^5$、$T=0$
• $\mathrm{subtask\, 6}(26\,\mathrm{pts}):$ $m, l \le 5 \cdot 10^6$、$T=1$

すべてのテストケースにおいて、$1 \le w_i \le 10^9$、$\max_{i=1}^{n} g(s_i) \le 10^{18}$、$|s_i| \ge 1$、$n \le 2 \cdot 10^5$ が保証されます。

$T=0$ のサブタスクでは、答えの絶対値が $(1, 10^8)$ の範囲にあることが保証されます。

$s_i$ は a、b、c、d の文字のみで構成されることが保証されます。

システムは $128$ ビット整数をサポートしています。