최대공약수

겐나디는 공부 중인 프로그래머다. 그는 두 양의 정수의 최대공약수를 구하는 유클리드 호제법을 배우고 있다.

겐나디는 정수 나눗셈 연산자(div)와 나머지 연산자(mod)를 자주 헷갈린다. 예를 들어 $37$ div $10 = 3$이고, $37$ mod $10 = 7$이다.

겐나디가 작성한 유클리드 알고리즘은 다음과 같다:

• 입력: 두 양의 정수 $x$와 $y$.
• $y > 0$인 동안 $x$를 $x$ div $y$로 바꾸고, 그다음 $x$와 $y$를 서로 바꾼다.
• 출력: $x$.

겐나디가 div 대신 mod를 썼다면 알고리즘은 $x$와 $y$의 최대공약수를 올바르게 찾았을 것이다. 그러나 이 버그에도 알고리즘이 올바르게 동작하는 경우가 있다.

겐나디는 $1 \le x, y \le n$을 만족하고, 알고리즘이 종료되며 올바른 답을 출력하는 모든 입력 쌍 $(x, y)$를 찾고자 한다. 이런 쌍을 사전순으로 나열한 것을 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$라 한다.

또한 $q$개의 질의가 주어진다. $i$번째 질의는 양의 정수 $p_i$이며, $p_i$번째 쌍의 $x_{p_i}$와 $y_{p_i}$를 출력하거나, $p_i > k$임을 보고한다.

첫 줄에 정수 $n$과 $q$가 주어진다. $n$은 입력 값의 상한이고, $q$는 질의의 개수다 ($1 \le n, q \le 2 \cdot 10^5$).

이후 $q$개의 줄에 각각 정수 $p_i$ 하나가 주어진다 ($1 \le p_i \le n^2$).

각 질의에 대해 두 정수를 출력한다. 알고리즘이 종료되고 올바른 답을 내는 쌍 중 사전순으로 $p_i$번째인 쌍의 $x_{p_i}$와 $y_{p_i}$를 출력한다. 그런 쌍이 $p_i$개보다 적으면 -1 -1을 출력한다.