Max(Fib(k)) та Min(Fib(k)) у Макса#5725
Випускник Максим (для друзів просто Макс) для експериментів використовує останніх цифр чисел Фібоначчі.
Максим вирішив увіковічнити своє ім'я в математиці і ввів для цілих чисел нові (як йому здається) функції Max та Min для чисел Фібоначчі. Під функцією Max(Fib(k)) він розуміє найбільшу цифру у запису -го числа Фібоначчі, а під Min(Fib(k)) — відповідно найменшу. Але йому не хочеться виконувати довгу арифметику, тому свою функцію він застосовує, як вже було сказано, лише до останніх -ти цифр у запису -го числа Фібоначчі.
Так само, як і Даша: якщо цифр не вистачає, то він не дописує спереду нічого — незначущі в даному випадку провідні нулі.
Нагадаємо, що числа Фібоначчі визначаються наступними рекурентними співвідношеннями:
Максим розв'язав свою задачку, а ви зможете?
У кожному рядку вхідного файлу задано єдине число (0 \leq k \leq 9223372036854775807).
Для кожного прикладу вхідних даних виведіть у окремому рядку через пропуск числа — відповідь до сформульованої задачі: спочатку Max(Fib(k)), а потім Min(Fib(k)).
Приклад 1