{"scoring":null,"notes":"","legend":"Gennady is an aspiring programmer. He is currently learning the Euclidean algorithm for computing the greatest common divisor of two positive integers.\r\n\r\nUnfortunately, Gennady sometimes confuses the integer division operator (denoted by \\t{div}) with the remainder operator (denoted by \\t{mod}). As an example, $37$ \\t{div} $10 = 3$ and $37$ \\t{mod} $10 = 7$.\r\n\r\nHere's Gennady's latest implementation of the Euclidean algorithm:\r\n\r\n\\begin{itemize}\r\n\\item \\textit{Input: two positive integers $x$ and $y$.}\r\n\r\n\\item \\textit{While $y > 0$:}\r\n\r\n\\, \\, \\, \\textit{Set $x = x$ \\t{div} $y$, then swap $x$ and $y$.}\r\n\r\n\\item \\textit{Output: $x$.}\r\n\r\n\\end{itemize}\r\n\r\nAs you can see, if Gennady used the \\t{mod} operator instead of the \\t{div} operator, his implementation would be correct: the algorithm above would successfully find the greatest common divisor of $x$ and $y$. However, it turns out that even with this nasty bug the algorithm sometimes works correctly! \r\n\r\nYou are given an integer $n$. Gennady is interested in finding all input pairs $(x, y)$ such that $1 \\le x, y \\le n$, the algorithm finishes, and produces the correct output. Let $(x_1, y_1), (x_2, y_2), \\ldots, (x_k, y_k)$ be all such pairs in lexicographic order (for all $1 \\le i < k$, either $x_i < x_{i+1}$, or $x_i = x_{i+1}$ and $y_i < y_{i+1}$).\r\n\r\nYou are also given $q$ queries. Query $i$ is a positive integer $p_i$, and you should print $x_{p_i}$ and $y_{p_i}$, or report that $p_i > k$.\r\n","authorLogin":"tourist","language":"english","timeLimit":5000,"output":"For each query, print two integers. These integers must either be $x_{p_i}$ and $y_{p_i}$, denoting the $p_i$-th input pair in lexicographic order such that the algorithm finishes and produces a correct output, or \\t{-1 -1} if there are less than $p_i$ such pairs.","inputFile":"stdin","outputFile":"stdout","input":"The first line contains two integers $n$ and $q$~--- the upper bound on the input values and the number of queries ($1 \\le n, q \\le 2 \\cdot 10^5$).\r\n\r\nEach of the next $q$ lines contains a single integer $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":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Геннадий Короткевич\\\\\r\n         Разработка: & Геннадий Короткевич\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nНаписав простое решение, перебирающее все пары, и примерно оценив рост числа подходящих пар в зависимости от $n$, можно понять, что для $n \\le 2 \\cdot 10^5$ хватит времени и памяти выписать все подходящие пары в один массив. Действительно, для $n = 2 \\cdot 10^5$ таких пар $4\\,480\\,708$.\r\n\r\nЗаметим, что после первой итерации алгоритма пара $(x, y)$ заменится на пару $(y, w)$, где $w = x$ \\t{div}~$y$. При этом произведение элементов в новой паре $y \\cdot w$ не превышает $x$, который в свою очередь не превышает $n$, а значит, возможных пар $(y, w)$ после первой итерации алгоритма всего $O(n \\log n)$, и их все можно перебрать.\r\n\r\nЗафиксируем некоторую такую пару вида $(y, w)$. Запустим алгоритм из условия до конца, пусть он вернёт некоторое число $g$. Если $y$ не делится на $g$, такая пара нам неинтересна. Иначе нам интересны все такие значения $x$, что $x$ \\t{div} $y = w$ и $\\operatorname{gcd}(x, y) = g$. Первое условие эквивалентно неравенствам $y \\cdot w \\le x < y \\cdot (w + 1)$, а из второго условия следует, что $x$ должно делиться на $g$. Значит, переберём все делящиеся на $g$ числа $x$ из диапазона $[y \\cdot w; y \\cdot (w + 1))$ и для каждого из них проверим условие $\\operatorname{gcd}(x, y) = g$. Таким образом мы и найдём все подходящие пары $(x, y)$."}