Dany jest zbiór $n$ ciągów znaków $s_1, s_2, \dots, s_n$. Każdy ciąg ma przypisaną wagę $w_i$.

Niech $S[l:r]$ oznacza podciąg ciągu $S$ od znaku na pozycji $l$ do znaku na pozycji $r$ (indeksowanie od $1$), a $f(S, T)$ oznacza liczbę wystąpień ciągu $T$ w ciągu $S$.

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

Dla każdego $h(S) = \frac{a}{b}$, gdzie $\gcd(a, b) = 1$, definiujemy $\hat{h}(S) = a \cdot b^{-1} \bmod 998244353$, gdzie $b^{-1}$ oznacza odwrotność modularną liczby $b$ w ciele $\mathbb{Z}_{998244353}$. Można dowieść, że we wszystkich przypadkach występujących w tym zadaniu odwrotność ta istnieje.

Dla wszystkich $1 \le i \le n$ oraz $1 \le j \le |s_i|$, oblicz $h(s_i[1:j])$. Uwaga: niektóre podzadania wymagają obliczenia tylko części odpowiedzi, szczegóły znajdują się w sekcjach Wejście i Wyjście.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $T$, oznaczające odpowiednio liczbę ciągów oraz typ testu.

Następnie $n$ linii zawiera ciąg znaków oraz liczbę całkowitą dodatnią, reprezentujące odpowiednio $s_i$ oraz $w_i$.

Wyjście

Dla podzadań z $T=0$, wypisz $h(s_1)$ w postaci liczby zmiennoprzecinkowej. Wynik uznaje się za poprawny, jeśli jego bezwzględny błąd względem odpowiedzi wzorcowej nie przekracza $10^{-4}$.

Dla podzadań z $T=1$, w celu ograniczenia ilości danych wyjściowych, należy wypisać $\oplus_{1 \le i \le n, 1 \le j \le |s_i|} \hat{h}(s_i[1:j])$, gdzie $\oplus$ oznacza operację bitowej alternatywy wykluczającej (XOR), czyli operator ^ w języku C++.

Przykład

Przykład 1

Wejście:

4 0
ababcdcd 0
ab 12
abc 20
bc 15

Wyjście:

15.666667

Przykład 2

Wejście:

4 1
ababcdcd 0
ab 12
abc 20
bc 15

Wyjście:

980069045

Podzadania

Niech $m = \sum_{i=1}^{n} |s_i|$ oraz $l = \max_{i=2}^{n} |s_i|$.

• $\mathrm{subtask\, 1}(3\,\mathrm{pkt}):$ $m, l \le 50$, $T=1$;
• $\mathrm{subtask\, 2}(14\,\mathrm{pkt}):$ $m, l \le 2000$, $T=1$;
• $\mathrm{subtask\, 3}(19\,\mathrm{pkt}):$ $m \le 10^5, l \le 50$, $T=0$;
• $\mathrm{subtask\, 4}(23\,\mathrm{pkt}):$ $m, l \le 10^5$, $T=0$;
• $\mathrm{subtask\, 5}(15\,\mathrm{pkt}):$ $m, l \le 3 \cdot 10^5$, $T=0$;
• $\mathrm{subtask\, 6}(26\,\mathrm{pkt}):$ $m, l \le 5 \cdot 10^6$, $T=1$;

Dla wszystkich testów gwarantuje się, że $1 \le w_i \le 10^9$, $\max_{i=1}^{n} g(s_i) \le 10^{18}$, $|s_i| \ge 1$ oraz $n \le 2 \cdot 10^5$.

Dla podzadań z $T=0$ gwarantuje się, że wartość bezwzględna odpowiedzi należy do przedziału $(1, 10^8)$.

Gwarantuje się, że $s_i$ składają się wyłącznie ze znaków a, b, c, d.

System wspiera liczby całkowite 128-bitowe.