Greatest Common Divisor
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Геннадий — начинающий программист. В настоящее время он изучает алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел.

К сожалению, Геннадий иногда путает оператор целочисленного деления (обозначается div) с оператором остатка (обозначается mod). Например, $$$37$$$ div $$$10 = 3$$$ и $$$37$$$ mod $$$10 = 7$$$.

Вот последняя реализация Геннадием алгоритма Евклида:

Как видите, если бы Геннадий использовал оператор mod вместо оператора div, его реализация была бы корректной: приведенный выше алгоритм успешно нашел бы наибольший общий делитель $$$x$$$ и $$$y$$$. Однако оказывается, что даже с этим неприятным багом алгоритм иногда работает корректно!

Вам дано целое число $$$n$$$. Геннадий заинтересован в том, чтобы найти все входные пары $$$(x, y)$$$ такие, что $$$1 \le x, y \le n$$$, алгоритм завершится и выдаст правильный результат. Пусть $$$(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$$$ запросов. Запрос $$$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$$$-ю входную пару в лексикографическом порядке, при которой алгоритм завершает работу и выдает правильный результат, либо -1 -1 если таких пар меньше $$$p_i$$$.

Пример

Входные данные
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