Greatest Common Divisor

Gennady is an aspiring programmer. He is learning the Euclidean algorithm for computing the greatest common divisor of two positive integers.

Gennady often confuses the integer division operator (div) with the remainder operator (mod). For example, $37$ div $10 = 3$ and $37$ mod $10 = 7$.

Here is Gennady's implementation of the Euclidean algorithm:

• Input: two positive integers $x$ and $y$.
• While $y > 0$: set $x = x$ div $y$, then swap $x$ and $y$.
• Output: $x$.

If Gennady used mod instead of div, the algorithm would correctly find the greatest common divisor of $x$ and $y$. However, even with this bug, the algorithm sometimes works correctly.

Gennady wants to find all input pairs $(x, y)$ such that $1 \le x, y \le n$, the algorithm finishes, and produces the correct output. Let $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$ be all such pairs in lexicographic order.

You are also given $q$ queries. Query $i$ is a positive integer $p_i$. Print $x_{p_i}$ and $y_{p_i}$, or report that $p_i > k$.

The first line contains two integers $n$ and $q$, the upper bound on the input values and the number of queries ($1 \le n, q \le 2 \cdot 10^5$).

Each of the next $q$ lines contains a single integer $p_i$ ($1 \le p_i \le n^2$).

For each query, print two integers: $x_{p_i}$ and $y_{p_i}$, the $p_i$-th pair in lexicographic order such that the algorithm finishes and produces a correct output. If there are fewer than $p_i$ such pairs, print -1 -1.