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

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

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

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

- Ввод: два натуральных числа $$$x$$$ и $$$y$$$.

- Пока $$$y > 0$$$:

  Установите $$$x = x$$$ div $$$y$$$, затем поменяйте местами $$$x$$$ и $$$y$$$.

- Вывод: $$$x$$$.

Как видите, если бы Геннадий использовал оператор 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