Gennady 是一位有抱负的程序员。他目前正在学习用于计算两个正整数最大公约数的欧几里得算法。

不幸的是，Gennady 有时会混淆整数除法运算符（记作 div）和取模运算符（记作 mod）。例如，$37 \text{ div } 10 = 3$ 且 $37 \text{ mod } 10 = 7$。

以下是 Gennady 最新的欧几里得算法实现：

• 输入：两个正整数 $x$ 和 $y$。
• 当 $y > 0$ 时： 令 $x = x \text{ div } y$，然后交换 $x$ 和 $y$。
• 输出：$x$。

如你所见，如果 Gennady 使用的是 mod 运算符而不是 div 运算符，他的实现将是正确的：上述算法将成功找到 $x$ 和 $y$ 的最大公约数。然而，事实证明，即使有这个讨厌的错误，该算法有时也能正确运行！

给定一个整数 $n$。Gennady 对寻找所有满足 $1 \le x, y \le n$、算法能够结束并产生正确输出的输入对 $(x, y)$ 感兴趣。设 $(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$ 为所有此类按字典序排列的对（对于所有 $1 \le i < k$，满足 $x_i < x_{i+1}$，或者 $x_i = x_{i+1}$ 且 $y_i < y_{i+1}$）。

你还需要处理 $q$ 个查询。第 $i$ 个查询是一个正整数 $p_i$，你需要输出 $x_{p_i}$ 和 $y_{p_i}$，或者报告 $p_i > k$。

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 输入值的上限和查询数量（$1 \le n, q \le 2 \cdot 10^5$）。

接下来的 $q$ 行，每行包含一个整数 $p_i$（$1 \le p_i \le n^2$）。

输出格式

对于每个查询，输出两个整数。这两个整数必须是 $x_{p_i}$ 和 $y_{p_i}$，表示按字典序排列的第 $p_i$ 个满足算法能够结束并产生正确输出的输入对；如果此类对的数量少于 $p_i$，则输出 -1 -1。

样例

样例输入 1

10 13
1
2
3
4
5
6
7
8
9
10
11
12
13

样例输出 1

2 2
3 3
4 2
4 4
5 5
6 6
7 7
8 8
9 3
9 9
10 4
10 10
-1 -1