Задача 68. Путаница ≡

Условие

Замяукали котята:

«Надоело нам мяукать!

Мы хотим, как поросята,

Хрюкать!»

А за ними и утята:

«Не желаем больше крякать!

Мы хотим, как лягушата,

Квакать!»

…

Корней Чуковский, "Путаница", 1926 г.

Путаница добралась и до чисел: x-й член последовательности Фибоначчи вдруг решил, что он равен d. Естественно, это вызвало цепную реакцию — все последующие члены этой последовательности тоже изменились. Выяснилось это случайно, когда обнаружилось, что k-й член последовательности равен n. Помогите математикам распутать путаницу и определить, какой член последовательности изменился первым и на сколько.

Напомним, что числа Фибоначчи — элементы числовой последовательности

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …

в которой первые два числа равны единицам, а каждое последующее число равно сумме двух предыдущих чисел.

Формат входных данных

Первая строка входного файла содержит натуральное число k — номер числа Фибоначчи. Вторая строка входного файла содержит целое число n — новое значение k-го числа Фибоначчи. Гарантируется, что новое значение не совпадает со старым.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите в первой строке одно натуральное число x — номер числа Фибоначчи, которое изменилось. Во второй строке выведите одно целое число — его новое значение d. Если подходящих ответов несколько, выведите ту пару чисел, у которой x меньше. Для определенности считайте, что самое первое число последовательности Фибоначчи не изменялось.

Ограничения

2 ≤ k ≤ 80

 − 10¹⁸ ≤ n ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере десятый член последовательности оказался равен 50. Такое изменение могло быть вызвано тремя причинами:

1) сам десятый член последовательности стал равен 50;

2) девятый член последовательности решил стать равным 29;

3) шестой член последовательности решил стать равным 7. Других возможностей нет, выводим пару с меньшим исходным номером.

Примеры тестов

10
50

6
7

3
0

2
-1