Известные числа Фиббоначи \(F_0, F_1, F_2,\ldots \) определяются следующим образом:
- \(F_0 = 0, F_1 = 1\).
- Для всех \(i \geq 2\): \(F_i = F_{i - 1} + F_{i - 2}\).
Дана возрастающая арифметическая прогрессия положительных целых чисел с \(n\) числами \((a, a + d, a + 2\cdot d,\ldots, a + (n - 1)\cdot d)\).
Вы должны найди другую возрастающую арифметическую прогрессию положительных целых чисел с \(n\) числами \((b, b + e, b + 2\cdot e,\ldots, b + (n - 1)\cdot e)\), такую что:
- \(0 < b, e < 2^{64}\),
- для всех \(0\leq i < n\), запись числа \(a + i \cdot d\) в десятичной системе счисления встречается как подстрока в строке, образованной последними \(18\)-ю цифрами десятичной записи числа \(F_{b + i \cdot e}\) (если это число содержит меньше чем \(18\) цифр, тогда рассмотрим все его цифры).
Выходные данные
Если не существует подходящей арифметической прогрессии, выведите единственное число \(-1\).
Иначе, выведите два целых числа \(b\) и \(e\), разделенных пробелом в единственной строке (\(0 < b, e < 2^{64}\)).
Если существует несколько возможных ответов, вы можете найти любой из них.
Примечание
В первом тесте, мы можем выбрать \((b, e) = (2, 1)\), потому что \(F_2 = 1, F_3 = 2, F_4 = 3\).
Во втором тесте, мы можем выбрать \((b, e) = (19, 5)\), потому что:
- \(F_{19} = 4181\) содержит \(1\);
- \(F_{24} = 46368\) содержит \(3\);
- \(F_{29} = 514229\) содержит \(5\);
- \(F_{34} = 5702887\) содержит \(7\);
- \(F_{39} = 63245986\) содержит \(9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 1
|
2 1
|
|
2
|
5 1 2
|
19 5
|