P1936 Chandelure

“The Story of Love and Sorrow V · Halloween,” Chapter 2. This problem can be frustrating; please read carefully.

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$.

A single integer $k$.

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

### Constraints - For $20\%$ of the testdata, $k \le 100$. - For $100\%$ of the testdata, $k \le 10^8$. Translated by ChatGPT 5