Tekstide erinevus

Kuulus tarkvarafirma Interplanetary Software Systems on loomas uut tekstitoimetit, mis suudab töödelda väga pikki väikestest ladina tähtedest koosnevaid ridu. Toote esimesel versioonil on ainult kaks funktsiooni:

1. tähe lisamine rea lõppu;
2. rea viimase tähe kustutamine (kui rida ei ole tühi).

Nimetame kahe sõne $s$ ja $t$ erinevuseks $\mathrm{diff}(s, t)$ minimaalset sõnest $s$ sõne $t$ saamiseks vajalike käskude arvu. Näiteks $\mathrm{diff}($'tests','text'$) = 5$: algul kustutame sõne 'tests' lõpust kolm viimast tähte ja seejärel lisame tulemuse lõppu tähed 'x' ja 't'.

Kirjutada programm, mis antud $N$ sõne $S_i$ kohta leiab $\mathrm{diff}(S_i, S_j)$ summa üle kõigi paaride, kus $1 \le i \le N$ ja $1 \le j \le N$.

Faili esimesel real on tekstiridade arv $N$ ($1 \le N \le 200\,000$) ja järgmisel $N$ real igaühel üks väikestest ladina tähtedest koosnev mittetühi sõne $S_i$. On teada, et $S_i$ pikkuste summa ei ületa $10^6$.

Faili ainsale reale väljastada otsitav erinevuste summa.