{"scoring":null,"notes":"","legend":"Геннадий --- начинающий программист. В настоящее время он изучает алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел.\r\n\r\nК сожалению, Геннадий иногда путает оператор целочисленного деления (обозначается \\t{div}) с оператором остатка (обозначается \\t{mod}). Например, $37$ \\t{div} $10 = 3$ и $37$ \\t{mod} $10 = 7$.\r\n\r\nВот последняя реализация Геннадием алгоритма Евклида:\r\n\r\n\\begin{itemize}\r\n\\item \\textit{Ввод: два натуральных числа $x$ и $y$.}\r\n\r\n\\item \\textit{Пока $y > 0$:}\r\n\r\n\\, \\, \\, \\textit{Установите $x = x$ \\t{div} $y$, затем поменяйте местами $x$ и $y$.}\r\n\r\n\\item \\textit{Вывод: $x$.}\r\n\r\n\\end{itemize}\r\n\r\nКак видите, если бы Геннадий использовал оператор \\t{mod} вместо оператора \\t{div}, его реализация была бы корректной: приведенный выше алгоритм успешно нашел бы наибольший общий делитель $x$ и $y$. Однако оказывается, что даже с этим неприятным багом алгоритм иногда работает корректно!\r\n\r\nВам дано целое число $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}$).\r\n\r\nВам также даются $q$ запросов. Запрос $i$ --- это положительное целое число $p_i$, и вы должны вывести $x_{p_i}$ и $y_{p_i}$ или сообщить, что $p_i > k$.","authorLogin":"tourist","language":"russian","timeLimit":5000,"output":"Для каждого запроса выведите два целых числа. Эти целые числа должны быть либо $x_{p_i}$ и $y_{p_i}$, обозначая $p_i$-ю входную пару в лексикографическом порядке, при которой алгоритм завершает работу и выдает правильный результат, либо \\t{-1 -1 } если таких пар меньше $p_i$.","inputFile":"stdin","outputFile":"stdout","input":"Первая строка содержит два целых числа $n$ и $q$ ~--- верхнюю границу входных значений и количество запросов ($1 \\le n, q \\le 2 \\cdot 10^5$).\r\n\r\nКаждая из следующих $q$ строк содержит одно целое число $p_i$ ($1 \\le p_i \\le n^2$).","authorName":"Gennady Korotkevich","sampleTests":[{"output":"2 2\r\n3 3\r\n4 2\r\n4 4\r\n5 5\r\n6 6\r\n7 7\r\n8 8\r\n9 3\r\n9 9\r\n10 4\r\n10 10\r\n-1 -1\r\n","input":"10 13\r\n1\r\n2\r\n3\r\n4\r\n5\r\n6\r\n7\r\n8\r\n9\r\n10\r\n11\r\n12\r\n13\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Greatest Common Divisor","interaction":null,"memoryLimit":536870912,"tutorial":""}