eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Найменше спільне субчисло

Найменше спільне субчисло

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB

Рядок цифр - це рядок символів, кожен з яких є цифрою від 0 до 9.

Субрядком рядка цифр назвемо число, запис якого може бути отриманий з заданого рядка викреслюванням деякої кількості символів (можливо нульової) і не має ведучих нулів.

Спільним субчислом двох рядків цифр називається число, яке є субчислом обох рядків.

Задано два рядки цифр. Потрібно знайти спільне субчисло максимальної довжини. Якщо таких чисел декілька, то потрібно вибрати з них мінімальне за величиною.

Вхідні дані

Вводиться два рядки цифр. Перший рядок містить не більше 3000 цифр - перший рядок цифр. Другий рядок містить другий рядок цифр - також не більше 3000 цифр.

Вихідні дані

У єдиному рядку виведіть одне ціле невід'ємне число - найменше спільне субчисло максимальної довжини для заданих рядків цифр. Якщо задані рядки не містять жодного спільного субчисла, то потрібно вивести число 0.

Приклад

Вхідні дані #1
00008
00000094
Вихідні дані #1
0
Джерело XX комплексна олімпіада "Турнір Чемпіонів", Командний тур, Вінниця, 30 квітня 2013 р.