B. Счастливая общая подпоследовательность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В математике подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Например, последовательность BDF — это подпоследовательность последовательности ABCDEF. Подстрока строки — это непрерывная подпоследовательность данной строки. Например, BCD — это подстрока ABCDEF.

Вам даны две строки s1, s2 и еще одна строка под названием virus. Ваша задача — найти наидлиннейшую общую подпоследовательность s1 и s2, такую, что она не содержит подстроку virus.

Входные данные

Входные данные состоят из трех строк, каждая в отдельной строке: s1, s2 и virus (1 ≤ |s1|, |s2|, |virus| ≤ 100). Каждая строка состоит исключительно из заглавных латинских букв.

Выходные данные

Выведите наидлиннейшую общую подпоследовательность s1, s2, не содержащую подстроку virus. Если имеется несколько решений, любое из них будет засчитано.

Если требуемой общей подпоследовательности нет, выведите 0.

Примеры
Входные данные
AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ
Выходные данные
ORZ
Входные данные
AA
A
A
Выходные данные
0