题目描述

给定 ( 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} \mod 998244353 )，其中 ( b^{-1} ) 表示 ( b ) 在 ( \mod 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
  

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