2-й этап Всеукраинской олимпиады по информатике 2013-2014 уч.г. 11 кл. г. Бердичев
Max(Fib(k)) и Min(Fib(k)) у Макса
Выпускник Максим (для друзей просто Макс) для экспериментов использует 5 последних цифр чисел Фибоначчи.
Максим решил увековечить своё имя в математике и ввёл для целых чисел новые (как ему кажется) функции Max и Min для чисел Фибоначчи. Под функцией Max(Fib(k)) он понимает наибольшую цифру в записи k-го числа Фибоначчи, а под Min(Fib(k)) - соответственно наименьшую. Но ему не хочется возиться с длинной арифметикой, поэтому свою функцию он применяет, как уже было сказано, только к последним 5-ти цифрам в записи k-го числа Фибоначчи.
Так же и Даша, если цифр не хватает, то он не дописывает спереди ничего не значащие в данном случае ведущие нули.
Напомним, что числа Фибоначчи определяются следующими рекуррентными соотношениями:
Максим решил свою задачку, а Вы сможете?
Input data
В каждой строке входного файла задано единственное число k (0 ≤ k ≤ 9223372036854775807).
Output data
Для каждого примера входных данных выведите в отдельной строке через пробел 2 числа - ответ на поставленную задачу, сначала Max(Fib(k)), а потом Min(Fib(k)).
Examples
0 1 2 37 14 135 23
1 1 1 1 2 2 9 1 6 0 8 2 8 3