F. Красивая задача с числами Фиббоначи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известные числа Фиббоначи $$$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$$$ цифр, тогда рассмотрим все его цифры).
Входные данные

Первая строка содержит три положительных целых числа $$$n$$$, $$$a$$$, $$$d$$$ ($$$1 \leq n, a, d, a + (n - 1) \cdot d < 10^6$$$).

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

Если не существует подходящей арифметической прогрессии, выведите единственное число $$$-1$$$.

Иначе, выведите два целых числа $$$b$$$ и $$$e$$$, разделенных пробелом в единственной строке ($$$0 < b, e < 2^{64}$$$).

Если существует несколько возможных ответов, вы можете найти любой из них.

Примеры
Входные данные
3 1 1
Выходные данные
2 1
Входные данные
5 1 2
Выходные данные
19 5
Примечание

В первом тесте, мы можем выбрать $$$(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$$$.