Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.
Однажды по почте Пете пришла строка s, состоящая только из цифр. Ему требуется найти строку, которая
- представляет собой счастливое число без лидирующих нулей,
- не пуста,
- содержится в s как подстрока максимальное количество раз.
Среди строк, для которых выполнены все три предыдущих условия, Петю интересует лексикографически минимальная. Найдите для Пети эту строку.
Выходные данные
В единственное строке выведите ответ на задачу Пети. Если искомой строки не существует, выведите «-1» (без кавычек).
Примечание
Лексикографическое сравнение строк реализует оператор < в современных языках программирования. Строка x лексикографически меньше строки y, если либо x является префиксом y, либо существует такое i (1 ≤ i ≤ min(|x|, |y|)), что xi < yi, и для любого j (1 ≤ j < i) xj = yj. Здесь |a| обозначает длину строки a.
В первом примере три условия выполняются для строк «4», «7» и «47». Из них лексикографически минимальная — «4».
Во втором примере s не имеет подстрок, являющихся счастливыми числами.
В третьем примере три условия выполняются только для строки «7».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
047
|
4
|
|
2
|
16
|
-1
|
|
3
|
472747
|
7
|