Весельчак У в очередной раз разрабатывает коварный план по захвату Вселенной. На этот раз он решил использовать передовые технологии, а именно --- биоинженерию. Он собирается создать особый вирус, который сможет заразить всех жителей Галактики.

С нуля создать смертоносный вирус --- задача не из простых, поэтому Весельчак У решил скомбинировать два существующих вируса. В его распоряжении находятся полностью расшифрованные геномы $n$ различных вирусов.

Геном каждого вируса представлен в виде строки, состоящей из строчных латинских букв. Для создания нового супер-вируса У планирует взять два различных вируса с геномами $s_1$ и $s_2$ и использовать специальную функцию совместимости:

$
L(s_1, s_2) = \text{lcp}(s_1, \text{reverse}(s_2)) + \text{lcp}(\text{reverse}(s_1), s_2)
$

где $\text{lcp}(x, y)$ --- длина наибольшего общего префикса строк $x$ и $y$, а $\text{reverse}(s)$ --- строка $s$, записанная в обратном порядке.

Крыс Глот куда-то пропал, и поэтому задача о поиске наилучшей комбинации вирусов легла на вас. Найдите пару с наибольшей совместимостью, а то сами знаете, что будет иначе.

\begin{center}
\includegraphics{tri5.png}
\end{center}
