4. Iné jazýčky

V reakcii na vedeckú štúdiu publikovanú v časopise sa profesor Labka rozhodol, že všetkým raz a navždy dokáže svoju dlhoročnú teóriu o možnostiach komunikácie medzi ľuďmi a mačkami.

Jeho teória je vskutku priamočiara – mačky hovoria tie isté slová, čo my (pretože sa ich všetky učia od svojich ľudských majiteľov), akurát nepoznajú naše hlásky, takže používajú iné, svoje. Takže vraj stačí zistiť, ktoré ľudské hlásky sa prekladajú na ktoré mačacie a naopak, a môžeme plne chápať mačaciu reč…

Vy samozrejme viete, že mačky podstatné informácie komunikujú výhradne telepaticky, takže jeho tvrdeniam neveríte.

Vašim cieľom je preto jeho hypotézu vyvrátiť, no musíte to spraviť veľmi opatrne, aby sa na vás akademická obec nepozerala cez labkyprsty (nájsť si takú metriku, ktorá by jeho tvrdeniam nedala šancu, by totiž nebolo dostatočne vedecké). Keďže profesor Labka pripúšťa rozdielny slovosled ľudskej a mačacej reči, musíte počítať aj s možnosťou, že preložiť sa občas dajú iba časti viet, nie vety celé. Samozrejme, ak takých častí bude príliš málo, alebo budú veľmi krátke, je jasné, že ide o štatisticky zanedbateľnú náhodu a jeho teória je úplný nezmysel.

Úloha

Dostanete dva reťazce dĺžky \(n\) zložené z písmen anglickej abecedy – vetu \(L\) povedanú človekom (veľkými písmenami) a vetu \(M\) (malými písmenami), o ktorej profesor Labka tvrdí, že je jej mačacím ekvivalentom.

Vašim cieľom je nájsť všetky preložiteľné intervaly – teda dvojice \(1 \leq i \leq j \leq n\) začiatku a konca podreťazcov – také, že podreťazec \(L[i, j]\) v ľudskom reťazci sa dá preložiť na podreťazec \(M[i, j]\) v mačacom reťazci.

Podreťazec sa dá preložiť práve vtedy, keď existuje nesporné kódovanie písmen z ľudského reťazca do mačacieho a naopak – teda keď platí: pokiaľ sú v jednom z podreťazcov dve rovnaké písmená, budú rovnaké aj písmená na zodpovedajúcich pozíciach v druhom podreťazci.

Keďže dlhšie podreťazce prinášajú viac dôkazov o (ne)správnosti hypotézy, považujeme ich za dôležitejší dôkazový materiál – pre každý preložiteľný interval teda zistite jeho dĺžku a odpovedzte ich celkový súčet.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) – dĺžka oboch reťazcov.

Na ďalších dvoch riadkoch sú reťazce \(L\) a \(M\), vždy v tomto poradí.

V jednotlivých sadách platia nasledovné obmedzenia:

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo – súčet dĺžok všetkých preložiteľných intervalov pre danú dvojicu reťazcov \(L\) a \(M\).

Príklady

Input:

3
AAB
baa

Output:

3

Preložiteľné sú len intervaly [1-1], [2-2], [3-3], keďže v intervaloch [1-2] a [2-3] kolidujú postupne preklady písmen A a a.

Input:

6
AHOJKY
mnauky

Output:

56

Žiadny z podreťazcov (ktorých je dokopy 21) nie je nepreložiteľný (nie je to prekvapivé, keďže v žiadnom z nich sa neopakujú písmená). Máme teda 1 interval dĺžky 6, 2 intervaly dĺžky 5… až po 6 intervalov dĺžky 1.

Input:

8
AHOJACAU
mnaumnau

Output:

54