Description

The great “Ai Yu Chou” stepped out of the Fairy-type Gym in high spirits—he had just earned the Fairy-type badge (applause)! But right outside, he ran into a group of パンプジン (Gourgeist) (Because today is Halloween)! What now? No worries—“Ai Yu Chou” still had a single Chandelure left (which perfectly counters Gourgeist). Perhaps because it was the last Pokémon still standing, Chandelure was extremely fired up and took down the whole group in one blow. Chandelure used a move *** (censored?!), which happened to satisfy the following three rules:

1. $m, n \in \{1, 2, \cdots, k\}$;
2. $(n^2 - m \times n - m^2)^2 = 1$;
3. $m, n$ are integers.

“Ai Yu Chou” is very happy. He wants to know the maximum value of $m^2 + n^2$, and in which case this maximum can be achieved. Can you help him? Please output $m$ and $n$.

Input Format

A single integer $k$.

Output Format

Two lines. The first line is the maximum value of $m$. The second line is the maximum value of $n$.

1995

m=987
n=1597

Hint

Constraints

• For $20\%$ of the testdata, $k \le 100$.
• For $100\%$ of the testdata, $k \le 10^8$.

Translated by ChatGPT 5