Anagrame

Se consideră șirul de litere mici ale alfabetului englez $A[1], \ldots, A[N]$.

Fie succesiunea de caractere alăturate din șir $A[x], A[x + 1],\ldots, A[y]$, unde $1 \leq x \leq y \leq N$, pe care o notăm cu $A[x, y]$.
Pentru oricare literă mică a alfabetului englez $\ell$, definim $\text{range}(\ell)$ ca fiind $0$, dacă $\ell$ apare cel mult o dată în $A[x, y]$. Altfel, valoarea $\text{range}(\ell)$ este egală cu diferența dintre cea mai mare și cea mai mică poziție pe care litera $\ell$ apare în $A[x, y]$.
Șirul suport asociat lui $A[x, y]$ este șirul de caractere minim lexicografic ce conține fiecare literă $\ell$ de $\text{range}(\ell)$ ori.

De exemplu, dacă șirul $A$ este șirul abdacgacd și considerăm $A[3, 8] = \texttt{dacgac}$, atunci $\text{range}(\texttt{a})=5 - 2 = 3$ (pentru că, în $A[3, 8]$, litera a apare pe pozițiile $2$ și $5$), $\text{range}(\texttt{c})=6-3=3$ și $\text{range}(\ell) = 0$ pentru toate celelalte litere $\ell \in \{\texttt{b}, \texttt{d}, \texttt{e}, \texttt{f}, \texttt{g}, \ldots, \texttt{z}\}$. Șirul suport asociat lui $A[3, 8]$ este, astfel, aaaccc.

Un șir de caractere $S_1$ este o anagramă a șirului $S_2$ dacă $S_1$ este identic cu $S_2$ sau dacă $S_1$ se poate obține din $S_2$ prin schimbarea ordinii caracterelor. De exemplu, șirul de caractere tamara este o anagramă a șirului armata. Două anagrame se consideră a fi distincte dacă ele diferă în cel puțin o poziție. De exemplu, șirul de caractere aab are trei anagrame distincte: aab, aba, baa.

Asupra șirului se efectuează două tipuri de operații:

• Actualizare: dându-se litera $c$ și poziția $poz$, se înlocuiește $A[poz]$ cu $c$.
• Generare: dându-se perechea $x, y$, se generează șirul suport al lui $A[x, y]$.

Cerință

Problema are două cerințe, cerința de rezolvat fiind dată de $C \in \{1, 2\}$. Pentru ambele cerințe, se dau șirul $A$ și $M$ operații care se vor efectua în ordine.
Dacă $\bm{C = 1}$: determinați șirul suport minim lexicografic dintre cele obținute în urma tuturor operațiilor de generare.
Dacă $\bm{C = 2}$: pentru fiecare operație de generare dată, determinați numărul de anagrame distincte ale șirului suport obținut, modulo $1 \ 999 \ 999 \ 973$.

Date de intrare

Pe prima linie a fișierului de intrare anagrame.in se află numerele naturale $C$, $N$ și $M$, unde $C$ este numărul cerinței ($1$ sau $2$), iar $N$ și $M$ au semnificația din enunț.
Pe a doua linie se află șirul $A$, cele $N$ caractere ale sale nefiind separate prin spații. Pe fiecare dintre următoarele $M$ linii se află datele care descriu câte o operație:

• O operație de actualizare este descrisă prin caracterul $c$ și un număr natural $poz$, cu semnificația din enunț.
• O operație de generare este descrisă prin perechea $x$, $y$ de numere naturale, cu semnificația din enunț.

Valorile aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire anagrame.out conține:
Dacă $\bm{C = 1}$: pe prima linie, șirul suport minim lexicografic cerut la cerința $1$.
Dacă $\bm{C = 2}$: pentru fiecare generare câte o linie, ce conține numărul cerut în cerința 2, în ordinea corespunzătoare generărilor date.

Restricții și precizări

• $1\leq N, M \leq 100 \ 000$
• $1\leq x \leq y \leq N$
• Se garantează că, pentru oricare operație de generare din testele de evaluare, șirul suport va conține cel puțin un caracter.
• În cadrul unei actualizări este permisă înlocuirea literei de pe poziția $poz$ cu ea însăși.
• Șirul de caractere $S[1], \ldots, S[k]$ este lexicografic mai mic decât șirul $T[1], \ldots, T[\ell]$ dacă (i)~$k < \ell$ și $S[i] = T[i]$ pentru oricare $1 \leq i \leq k$, sau (ii)~există un $1 \leq i \leq \min(k,\ell)$ astfel încât $S[1] = T[1], \ldots, S[i-1] = T[i-1]$ și $S[i]<T[i]$.

Exemplul 1

anagrame.in

1 5 5
abcar
b 3
1 4
r 4
r 2
2 4

anagrame.out

aaab

Explicație

După prima actualizare, șirul $A$ devine abbar. A doua operație este o generare. Șirul suport obținut pentru abba este aaab. După următoarele două actualizări, șirul $A$ devine arbrr, iar șirul suport pentru rbr corespunzător celei de a doua generări este rr. Șirul suport minim lexicografic dintre cele două obținute este aaab.

Exemplul 2

anagrame.in

2 5 5
abcar
b 3
1 4
r 4
r 2
2 4

anagrame.out

4
1

Explicație

Pentru prima generare $(1,4)$ șirul suport obținut este aaab, care are patru anagrame distincte: aaab, aaba, abaa, baaa. După următoarele două operații, șirul suport pentru rbr este rr, care are o singură anagramă.