Геннадий — начинающий программист. В настоящее время он изучает алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел.
К сожалению, Геннадий иногда путает оператор целочисленного деления (обозначается div) с оператором остатка (обозначается mod). Например, $$$37$$$ div $$$10 = 3$$$ и $$$37$$$ mod $$$10 = 7$$$.
Вот последняя реализация Геннадием алгоритма Евклида:
Установите $$$x = x$$$ div $$$y$$$, затем поменяйте местами $$$x$$$ и $$$y$$$.
Как видите, если бы Геннадий использовал оператор 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