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