Танд $n$ урттай $S$ тэмдэгт мөр өгөгдөнө. Тэмдэгт тус бүр нь Англи хэлний эхний $m$ жижиг үсгүүдийн аль нэг нь байна.

$S$ ба $T$ тэмдэгт мөрүүдийн Хамгийн урт нийтлэг дараалал (ХУНД) нь $n-1$ байх Англи хэлний эхний $m$ жижиг үсгүүдээс $n$ урттай, ялгаатай $T$ тэмдэгт мөр хэд үүсэхийг тооцоолоорой.

$S$ ба $T$-д аль алинд нь $C$ байх $S$ ба $T$ 2 тэмдэгт мөрийн ХУНД нь хамгийн урт $C$ тэмдэгт мөр байдгийг санаарай.

Оролт

Эхний мөр нь $S$ тэмдэгт мөрийн урт болон тэмдэгт мөр үүсгэх Англи хэлний эхний хэдэн тэмдэгт ашиглахыг харуулах $n$ ба $m$ 2 тоог агуулна.($1≤n≤100 000$, $2≤m≤26$).

2 дахь мөр нь $S$ тэмдэгт мөрийг агуулна.

Гаралт

Хариуг агуулах ганц мөрийг хэвлээрэй.

Эхний жишээнд, $6$ боломжит $T$ тэмдэгт мөр байна: $aab$, $aac$, $aba$, $aca$, $baa$, $caa$.

2 дахь жишээнд, $11$ боломжит $T$ тэмдэгт мөр байна: $aaa$, $aac$, $aba$, $abb$, $abc$, $aca$, $acb$, $baa$, $bab$, $caa$, $cab$.

3 дахь жишээнд, ганцхан боломжит $T$ тэмдэгт байх ба тэр нь $b$ байна.