Maximizing the Sum of Squares under a Diophantine Constraint

In this problem, you are given a positive integer k. You need to find two integers m and n in the set \(\{1, 2, \ldots, k\}\) satisfying the following conditions:

1. \(m, n \in \{1, 2, \dots, k\}\).
2. \((n^2 - m \times n - m^2)^2 = 1\), i.e. \(n^2 - m\,n - m^2 = \pm 1\).
3. m and n are integers.

Your task is to determine the pair \((m, n)\) that maximizes \(m^2 + n^2\) among all pairs satisfying the conditions. Output the corresponding values of m and n.

Note: It is guaranteed that at least one such pair exists for any valid \(k\), as for example when \(k = 1\), the pair \((1,1)\) satisfies the condition since \(1^2 - 1 \times 1 -1^2 = -1\) and \((-1)^2 = 1\).

inputFormat

The input consists of a single integer k (\(1 \leq k \leq 10^4\)).

outputFormat

Output two integers m and n separated by a space that maximize \(m^2+n^2\) among all valid pairs \((m,n)\) satisfying \((n^2 - m\,n - m^2)^2 = 1\).

sample

1

1 1