问题描述

给定 $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$ 意义下的乘法逆元。

对于所有 $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

输出样例1

15.666667

数据范围

记 $m=\sum_{i=1}^{n}|s_i|,l=\max_{i=2}^{n}|s_i|$。

对于所有测试点保证：

• $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 构成