Max(Fib(k)) and Min(Fib(k)) at Max's#5725
Graduate Maksym, affectionately known as Max by his friends, is conducting experiments using the last digits of Fibonacci numbers.
In his quest to leave a mark in mathematics, Maksym has defined two new functions for Fibonacci numbers, which he calls Max and Min. The function Max(Fib(k)) represents the largest digit in the last digits of the -th Fibonacci number, while Min(Fib(k)) represents the smallest digit in the same segment. To avoid dealing with large numbers, he only considers these last digits.
If the -th Fibonacci number has fewer than digits, Maksym does not add leading zeros.
Recall that Fibonacci numbers are defined by the following recurrence relations:
Maksym has already solved this problem for himself. Can you do the same?
Each line of the input file contains a single number (0 \leq k \leq 9223372036854775807).
For each input number, output on a separate line numbers separated by a space: first Max(Fib(k)), then Min(Fib(k)).
Example 1