Задача Строчечки

Описание

Строка A = a ₁ a ₂ ...a _n является подстрокой строки B = b ₁ b ₂ ...b _m , если существует такое число k (1 <= k <= m-n+1), что a ₁ = b _k , a ₂ = b _k+1 , ..., a _n = b _k+n-1 .

Строка B называется надстрокой A, если A является подстрокой B.

Строка A = a ₁ a ₂ ...a _n лексикографически меньше строки B = b ₁ b ₂ ...b _m , если для некоторого k и для всех 1 <= t <= k верно a _t = b _t и либо a _k+1 < b _k+1 , либо длина A равна k, а длина B больше k. Даны S и T. Необходимо найти строку, являющуюся одновременно подстрокой S и надстрокой T. Если таких строк несколько, выведите самую длинную из них. Если строк наибольшей длины несколько, выведите лексикографически наименьшую.

Формат входных данных

В первой строке находится строка S (1 <= |S| <= 4000). Во второй строке находится строка T (1 <= |T| <= 4000). Обе строки состоят из строчных латинских букв. Здесь как |S| и |T| обозначены соответственно длины строк S и T.

Формат выходных данных

В выходной файл выведите искомую строку или "NO SOLUTION" (без кавычек), если такой строки не существует.