题目描述

Gennady 正在学习用欧几里得算法计算两个正整数的最大公约数。

不幸的是，他有时会把整数除法运算符 div 与取余运算符 mod 混淆。例如：

$$37\mathbin{\mathrm{div}}10=3, \qquad 37\mathbin{\mathrm{mod}}10=7.$$

他最近写出了下面的“欧几里得算法”：

1. 输入两个正整数 $x,y$；
2. 当 $y>0$ 时：
   • 令 $x=x\mathbin{\mathrm{div}}y$；
   • 交换 $x$ 与 $y$；
3. 输出 $x$。

如果把程序中的 div 换成 mod，它就是正确的欧几里得算法。但令人意外的是，即使存在这个错误，程序在某些输入上仍然会终止并输出真正的 $\gcd(x,y)$。

给定整数 $n$，考虑所有满足以下条件的有序对 $(x,y)$：

• $1\le x,y\le n$；
• 上述错误算法会终止；
• 算法输出恰好等于 $\gcd(x,y)$。

按字典序排列所有合法有序对：

$$(x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k).$$

也就是说，对任意 $1\le i<k$，要么 $x_i<x_{i+1}$，要么 $x_i=x_{i+1}$ 且 $y_i<y_{i+1}$。

接下来给出 $q$ 个查询。对于每个查询 $p_i$，输出第 $p_i$ 个合法有序对；若 $p_i>k$，则报告不存在。

输入格式

第一行包含两个整数 $n,q$。

接下来 $q$ 行，每行包含一个整数 $p_i$。

数据范围

$$1\le n,q\le 2\cdot 10^5,$$ $$1\le p_i\le n^2.$$

输出格式

对于每个查询：

• 若至少存在 $p_i$ 个合法有序对，输出 $x_{p_i}$ 和 $y_{p_i}$；
• 否则输出 -1 -1。

样例

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

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