405868: GYM102136 J Restore the sequence
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
J. Restore the sequencetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output1 ≤ N ≤ 106 Output
Vanya constructed a sequence fi according to the following rule:
- f0 = x, f1 = y;
- fi = fi - 1 + fi - 2, i > 1.
Unfortunately, Vanya lost this sequence. However, he memorized one number N, which belongs to this sequence. He also remembers that all elements of the sequence are non-negative integers.
Help Vanya find such x and y, by which he can restore the sequence. Vanya understands that there can be many answers, so he wants the value of x + y to be as small as possible, and in case there are several such pairs, x should be the minimum possible.
InputThe single line contains one integer N — the number that Vanya memorized.
In the single line output two integers x and y — the initial parameters of the sequence.
ExamplesInput42Output
0 2Input
19Output
3 2