Given $n$ strings $s_1, s_2, \dots, s_n$. Each string has a weight $w_i$.

Let $S[l:r]$ be the substring of $S$ from the $l$-th character to the $r$-th character (1-indexed), and let $f(S, T)$ be the number of occurrences of string $T$ in string $S$.

Let $g(S) = \sum_{i=1}^{n} w_i \times f(S, s_i)$ and $h(S) = \max_{1 \le l \le r \le |S|} \frac{g(S[l:r])}{r-l+1}$.

For any $h(S) = \frac{a}{b}$, where $\gcd(a, b) = 1$, we define $\hat{h}(S) = a \cdot b^{-1} \bmod 998244353$, where $b^{-1}$ is the multiplicative inverse of $b$ modulo $998244353$. It can be proven that in all cases encountered in this problem, $b$ has a multiplicative inverse.

For all $1 \le i \le n$ and $1 \le j \le |s_i|$, calculate $h(s_i[1:j])$. Note that some subtasks only require a partial answer; see the Input and Output sections for details.

Input

The first line contains two integers $n$ and $T$, representing the number of strings and the test case type, respectively.

The next $n$ lines each contain a string and a positive integer, representing $s_i$ and $w_i$.

Output

For the subtask where $T=0$, output $h(s_1)$ as a floating-point number. The result is considered correct if the absolute error compared to the standard output is within $10^{-4}$.

For the subtask where $T=1$, to reduce the output size, you only need to output $\oplus_{1 \le i \le n, 1 \le j \le |s_i|} \hat{h}(s_i[1:j])$, where $\oplus$ denotes the bitwise XOR operation, i.e., the ^ operator in C++.

Examples

Input 1

4 0
ababcdcd 0
ab 12
abc 20
bc 15

Output 1

15.666667

Input 2

4 1
ababcdcd 0
ab 12
abc 20
bc 15

Output 2

980069045

Subtasks

Let $m = \sum_{i=1}^{n} |s_i|$ and $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$;

For all test cases, it is guaranteed that $1 \le w_i \le 10^9$, $\max_{i=1}^{n} g(s_i) \le 10^{18}$, $|s_i| \ge 1$, and $n \le 2 \cdot 10^5$.

For subtasks with $T=0$, it is guaranteed that the absolute value of the answer lies in the interval $(1, 10^8)$.

It is guaranteed that $s_i$ consists only of characters a, b, c, and d.

The system supports 128-bit integers.