题目描述

给定 $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])$。注意一些 subtask 仅需求出部分答案，详见输入输出格式。

输入格式

第一行包含两个整数 $n,T$，分别表示字符串数和该测试点类型。

接下来 $n$ 行，每行一个字符串和一个正整数，分别表示 $s_i$ 和 $w_i$。

输出格式

对于 $T=0$ 的subtask，请以浮点数形式输出 $h(s_1)$。输出结果与标准输出的绝对误差在 $10^{-4}$ 之内即算正确。

对于 $T=1$ 的subtask，为减少输出量，你只需输出 $\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

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