Даны $n$ строк $s_1, s_2, \dots, 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}$.

Для любого $h(S) = \frac{a}{b}$, где $\gcd(a, b) = 1$, определим $\hat{h}(S) = a \cdot b^{-1} \bmod 998244353$, где $b^{-1}$ — мультипликативная инверсия $b$ по модулю $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$ обозначает операцию побитового исключающего ИЛИ (XOR), соответствующую оператору ^ в языке 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-битные целые числа.