33832번 - Podciągi 다국어

Dane jest słowo $s$ o długości $n$ nad alfabetem $\{$a, b, c, d, e, f$\}$. Na słowie tym wykonywanych zostanie $q$ operacji. Każda operacja polega na zamianie dokładnie jednej litery w słowie.

Rozważmy multizbiór $X_s$ wszystkich podciągów $s$, czyli słów powstających przez usunięcie pewnego podzbioru liter ze słowa $s$.

Twoim zadaniem jest utrzymywać informację o liczbie różnych niepustych słów $t$, które w $X_s$ występują co najmniej dwa razy.

Dla przykładu, w ciągu ababa jest $6$ takich słów:

• Słowo a występuje w $X_s$ trzy razy.
• Słowo b występuje w $X_s$ dwa razy.
• Słowo ab występuje w $X_s$ trzy razy (usuwając z $s$ litery na pozycjach $3$, $4$, $5$; $2$, $3$, $5$ lub $1$, $2$, $5$).
• Słowo ba występuje w $X_s$ trzy razy (usuwając z $s$ litery na pozycjach $1$, $4$, $5$; $1$, $3$, $4$ lub $1$, $2$, $3$).
• Słowo aa występuje w $X_s$ trzy razy (usuwając z $s$ litery na pozycjach $2$, $4$, $5$; $2$, $3$, $4$ lub $1$, $2$, $4$).
• Słowo aba występuje w $X_s$ cztery razy (usuwając z $s$ litery na pozycjach $4$, $5$; $3$, $4$; $2$, $3$ lub $1$, $2$).

Oblicz liczbę takich słów $t$ w zbiorze $X_s$ dla początkowego słowa $s$ oraz dla słów $s$ po każdej z operacji. Ponieważ liczby te mogą być dość duże, wypisz ich reszty z dzielenia przez $998\, 244\, 353$.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $n$ oraz $q$ ($3 ≤ n ≤ 50\, 000$, $0 ≤ q ≤ 50\, 000$), gdzie $n$ oznacza długość słowa, a $q$ oznacza liczbę operacji.

W drugim wierszu wejścia znajduje się $n$-literowe słowo złożone z małych liter alfabetu angielskiego. Ciąg ten składa się jedynie z liter od a do f.

W kolejnych $q$ wierszach znajdują się opisy operacji. Każdy opis składa się z liczby całkowitej $p_i$ ($1 ≤ p_i ≤ n$) oraz litery $z_i$ ($z_i ∈ \{$a, b, c, d, e, f$\}$) i oznacza zamianę litery na pozycji $p_i$ w słowie s na literę $z_i$.

Na wyjściu powinno znaleźć się $q + 1$ wierszy; w $i$-tym wierszu powinna znaleźć się jedna liczba całkowita: liczba różnych słów $t$, które występują co najmniej dwa razy jako podciąg słowa $s$. Wszystkie wyniki należy podać modulo $998\, 244\, 353$.

Wyjaśnienie przykładu: Oto stan słowa s po kolejnych aktualizacjach oraz słów $t$, które występują jako podciąg $s$ przynajmniej dwa razy:

• słowo: abca, podciągi: $\{$a$\}$,
• słowo: abca, podciągi: $\{$a$\}$,
• słowo: abcd, podciągi: $\{\}$,
• słowo: accd, podciągi: $\{$ac, acd, cd, c$\}$.