給定 $n$ 個字串 $s_1, s_2, \cdots, 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$ 的最大公因數為 $1$，規定 $\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])$。注意一些子任務僅需輸出部分答案，詳見輸入輸出格式。

輸入格式

第一行包含兩個整數 $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

範例 1 輸出

15.666667

範例 2 輸入

4 1
ababcdcd 0
ab 12
abc 20
bc 15

範例 2 輸出

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$ 位元整數。