armonioase

Gigel este un împătimit al jocurilor și petrece ore întregi tastând pentru a-și învinge adversarii virtuali. Într-o zi, el a descoperit că tastatura lui a început să se comporte ciudat pentru două din tastele utilizate intens pentru jocurile sale: tasta w și tasta m. Mai exact, Gigel a observat că atunci când dorește să scrie un mesaj și apasă tasta w uneori în mesaj este inclusă litera w, dar alteori, pentru o singură apăsare a tastei w, este inclusă secvența vv. În mod similar, când încearcă să utilizeze tasta m: la o apăsare a tastei m uneori îi apare m în mesaj, dar alteori apare secvența nn. Orice altă tastă funcționează corect. Spre exemplu, atunci când tastează cuvântul warm el poate obține unul din următoarele cuvinte: warm – dacă totul funcționează corect; vvarm – dacă pentru tasta w apare vv; warnn – dacă pentru tasta m apare nn; vvarnn – dacă pentru tasta w apare vv și pentru tasta m apare nn.

Gigel a descoperit un joc pentru care trebuie să tasteze șiruri armonioase. Un șir este considerat armonios dacă conține cel puțin o literă m și numărul de litere w din șir divide numărul de litere m care apar în acel șir. Spre exemplu, șirul mawnmvwbdmem este considerat armonios, deoarece conține $2$ apariții pentru w și $4$ apariții pentru m, dar șirurile awnmvwbdmem, mawnmvwbdme sau wawnmvwbdmwe nu sunt armonioase.

Definim următoarele două operații care se pot aplica unui șir de caractere:

1. dacă în șir identificăm două litere consecutive vv le înlocuim cu litera w;
2. dacă în șir identificăm două litere consecutive nn le înlocuim cu litera m.

De exemplu, aplicând operațiile de mai sus șirul vvarnnn poate fi transformat în: warnnn, warmn, warnm, vvarmn, vvarnm.

Cerințe

Dat fiind un șir format din litere mici ale alfabetului englez, scrieți un program care să rezolve următoarele cerințe:

1. pentru o succesiune de $N$ valori date $K_1, K_2, \ldots, K_N$, să se determine pentru fiecare valoare $K_i$ $(1 \leq i \leq N)$ dacă, prin aplicarea a $0$, $1$ sau mai multe operații descrise în enunț, se poate transforma șirul dat într-un șir armonios care să conțină exact $K_i$ apariții pentru m;
2. să se determine numărul de perechi distincte de forma $(val_1, val_2)$ cu proprietatea că, prin aplicarea a $0$, $1$ sau mai multe operații din enunț, putem transforma șirul dat într-un șir armonios care să conțină exact $val_1$ apariții pentru w și $val_2$ apariții pentru m;
3. să se determine lungimea maximă a unei secvențe armonioase din șirul dat, fără aplicarea niciunei operații; o secvență este formată din litere situate pe poziții consecutive în șir.

Date de intrare

Fișierul de intrare armonioase.in conține pe prima linie numărul natural $C$ reprezentând cerința care trebuie rezolvată ($1$, $2$ sau $3$). Pe a doua linie se află un șir format din litere mici ale alfabetului englez. Dacă $C = 1$, pe a treia linie se află numărul natural $N$, iar pe următoarele $N$ linii sunt scrise valorile $K_1, K_2, \ldots, K_N$, câte o valoare pe o linie.

Date de ieșire

Fișierul de ieșire armonioase.out conține:

• dacă $C = 1$: $N$ linii; pe linia $i$ $(1 \leq i \leq N)$ este scris mesajul DA dacă, prin aplicarea a $0$, $1$ sau mai multe operații din enunț, se poate transforma șirul dat într-un șir armonios care să conțină exact $K_i$ apariții pentru m, respectiv mesajul NU în caz contrar.
• dacă $C = 2$ sau $3$: o singură linie pe care este scris un număr natural reprezentând răspunsul la cerința $C$.

Restricții și precizări

• lungimea șirului dat $2 \leq lg \leq 200 \ 000$;
• $2 \leq N \leq 10 \ 000$;
• $1 \leq K_i < lg$, pentru orice $1 \leq i \leq N$;
• Se garantează că în șirul dat există cel puțin o literă w și o literă m.

Exemplul 1

armonioase.in

1
annnvvwmmbnnwmavmwv
2
5
6

armonioase.out

NU
DA

Explicație

$C = 1$. Șirul conține $4$ litere m și $3$ litere w.

Nu putem obține un șir armonios cu $K_1 = 5$ apariții ale literei m, deoarece $5$ are exact $2$ divizori ($1$ și $5$), deci ar trebui să avem fie $1$, fie $5$ litere w. Fiindcă există deja $3$ litere w și doar o pereche vv care ar putea fi transformată într-un w, nu putem obține $5$ litere w.

Pentru $K_2 = 6$ răspunsul este DA, deoarece $3$ (numărul de litere w) divide pe $6$.

Exemplul 2

armonioase.in

2
vvamnnnvvw

armonioase.out

3

Explicație

$C = 2$.

Perechile pentru care putem obține un șir armonios sunt: $(1, 1)$ (exemplu: vvamnnnvvw), $(1, 2)$ (exemplu: vvammnvvw) și $(2, 2)$ (exemplu: wammnvvw).

Exemplul 3

armonioase.in

3
avwmmbwmamw

armonioase.out

10

Explicație

$C = 3$.

Cea mai lungă secvență armonioasă este avwmmbwmam, care conține două apariții ale literei w și $4$ apariții ale literei m. Cum $2 \mid 4$, secvența este armonioasă. Aceasta are lungimea $10$ și nu există nicio secvență mai lungă care să respecte condiția.