7. Celistvé tabule

Kde bolo, tam bolo, pri rozostavanej diaľnici stála tabuľa “nevyrušujte, tu staviame diaľnice!”. Až jedného dňa vietor zavial a tabuľa sa rozpadla na maličké kúsky. Takže nielen diaľnicu treba stavať, ale aj novú tabuľu.

Lenže robotníci na stavbe si myslia, že pôvodný nápis už začínal byť nudný (napokon, už dlho žiadnu diaľnicu nestavali). Radi by ho nahradili iným humorným nápisom. Ale nanešťastie nemajú dosť farby, aby namaľovali nový nápis. Ani z pôvodnej tabule nezostali vôbec žiadne použiteľné zvyšky.

Našťastie objavili, že medzi stavebnými materiálmi majú pripravené množstvo menších tabúľ, rovno aj s nápismi.

Nanešťastie, nikomu sa žiadny z existujúcich nápisov nepáčil.

Našťastie jeden robotník dostal nápad: “čo keby sme zobrali dve tabule a dali ich vedľa seba, aby vzniklo niečo smiešne?”

Nanešťastie, spájať tabule nie je len tak (veď sme videli, ako ľahko sa tá stará rozpadla). Keby vyrobili nápis len tak prilepením dvoch tabúľ stranou k sebe, za chvíľu by bolo po ňom.

Našťastie dostali ďalší geniálny nápad: nemohli by proste zobrať tretiu tabuľu, prelepiť ju cez dve spojené tabule, a takto dostať celistvú tabuľu?

Nanešťastie, to nemôžete len tak lepiť všakovaté tabule cez tabule, čo keby sa vrchná tabuľa odlepila a ukázalo sa, že zakrývala úplne iný nápis! Treba aby sa nápis na tretej tabuli presne zhodoval so zakrytým textom na prvých dvoch. A samozrejme, tretia tabuľa musí zakrývať časť oboch spodných, aby to držalo pokope.

Tak, všetko je vyriešené, a už len ostáva vymyslieť ktorú trojicu tabúľ použijete na výrobu novej (celistvej) tabule.

Našťastie, na to ste tu vy, aby ste zistili z koľkých možností si môžu vyberať!

Úloha

Máte \(n\) kôpok tabúľ označených \(1\) až \(n\). Na kôpke \(i\) je množstvo tabúľ s nápisom \(w_i\). Spočítajte počet možností, koľkými spôsobmi sa dajú správne zlepiť. Správne zlepené tabule vyzerajú napríklad takto:

(Ľ) DIAĽNICE..........
(P) ........NASTAVANIE
(S) ......CENA........

(Ľ)avá a (P)ravá tabuľa sa musia tesne dotýkať, ale nie prekrývať. (S)tredná tabuľa sa musí aspoň jedným znakom prekrývať s ľavou aj pravou tabuľou. Jej nápis sa musí zhodovať so zakrytým textom, a nesmie prečnievať za ľavý okraj ľavej ani pravý okraj pravej tabule.

• Toto nie je dobrá možnosť, lebo nápis na strednej tabuli sa nezhoduje so zakrytým textom:

  (Ľ) DIAĽNICE.........
  (P) ........NESTAVAME
  (S) ......CENA.......

• Toto nie je dobrá možnosť, lebo stredná tabuľa zakrýva iba pravú, takže ľavá môže ľahko odpadnúť:

  (Ľ) DIAĽNICA......
  (P) ........NEBUDE
  (S) ..........BUDE

• Toto nie je dobrá možnosť, lebo stredná tabuľa pokračuje za okraj pravej:

  (Ľ) POCHOPIT......
  (P) ........NAVOD.
  (S) .....PITNAVODA

Počítanie možností

Každá možnosť je jedinečne identifikovaná štyrmi parametrami: číslom kôpky, z ktorej berieme ľavú tabuľu, číslom kôpky, z ktorej berieme pravú tabuľu, číslom kôpky, z ktorej berieme strednú tabuľu, a miestom, kde priložíme strednú tabuľu cez ľavú a pravú. Ak sa čokoľvek z toho líši, ráta sa to ako ďalšia možnosť. Nejde len o počet rôznych výsledných viditeľných nápisov, ale o všetky rôzne spôsoby, ako ich zložiť.

Ak sú viaceré možné pozície, kde v texte sa dá priložiť nejaká stredná tabuľa na nejakú ľavú a pravú, započítajte každú pozíciu ako ďalšiu možnosť.

Ak majú viaceré kôpky tabúľ rovnaký nápis, započítajte samostatne každú platnú kombináciu čísel kôpok.

Na každej kôpke je veľa kusov tabúľ s tým istým nápisom \(w_i\) (“veľa” znamená “aspoň 3 kusy”). Takže viaceré tabule (ľavá, pravá a/alebo stredná) môžu mať ten istý nápis, aj keby bola na vstupe len jedna kôpka s takým nápisom. Inými slovami, aj možnosti, ktoré používajú to isté číslo kôpky na viacerých miestach, sú platné.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 2\cdot 10^5\)) udávajúce počet kôpok tabúľ.

Na každom z nasledujúcich \(n\) riadkov je jeden reťazec \(w_i\) pozostávajúci z veľkých písmen anglickej abecedy – nápis na tabuliach na kôpke \(i\). Nápisy nemusia nutne byť rôzne.

Celkový súčet dĺžiek reťazcov na vstupe nepresiahne \(10^6\).

Existuje \(8\) sád vstupov. Majú nasledovné obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo: počet rôznych správnych možností, ako zlepiť tabule zo vstupu.

Príklady

Input:

7
DIALNICE
DIALNICA
NASTAVANIE
NESTAVAME
NEBUDE
BUDE
CENA

Output:

1

Jediná možnosť je hore uvedená trojica tabúľ (DIALNICE, NASTAVANIE, CENA) so znázornenou pozíciou.

Input:

3
A
BABA
ABAB

Output:

8

Nápis A je príliš krátky aby išiel použiť ako stredná tabuľa, ale môžeme ho použiť ako ľavú alebo pravú tabuľu a úplne ho zakryť. Všimnite si, že existujú viaceré možnosti ktoré vytvoria rovnaký nápis, napr. pri Ľ=BABA P=BABA S=ABAB môžeme nalepiť strednú tabuľu na pozíciu doľava na B[ABAB]ABA alebo doprava na BAB[ABAB]A. Tiež si všimnite, že sme v tomto prípade zobrali ľavú aj pravú tabuľu z tej istej kôpky (BABA). Dokonca existujú aj možnosti, kde zoberieme všetky tri tabule z tej istej kôpky.

Input:

2
HAHA
HAHA

Output:

8

Môžeme si vybrať, či ľavú tabuľu vezmeme z kôpky 1 alebo kôpky 2, pravú z 1 alebo 2, a strednú z 1 alebo 2, čo sa technicky ráta ako \(2^3=8\) rôznych možností. V každom prípade vznikne nápis HAHAHAHA, a strednú tabuľu musíme umiestniť tak, aby zakrývala to stredné HAHA.