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 output

Vanya constructed a sequence fi according to the following rule:

  1. f0 = x, f1 = y;
  2. 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.

Input

The single line contains one integer N — the number that Vanya memorized.

1 ≤ N ≤ 106
Output

In the single line output two integers x and y — the initial parameters of the sequence.

ExamplesInput
42
Output
0 2
Input
19
Output
3 2

加入题单

上一题 下一题 算法标签: