인수분해

정수 인수분해는 여러 암호 체계에서 중요한 역할을 한다. 양의 합성수 $n$이 주어졌을 때 $n = pq$이고 $1 < p \le q < n$인 두 양의 정수 $p$와 $q$를 찾는 문제다. 하지만 이는 잘 알려진 NP-중간 후보로, 다항 시간에 해결하는 알고리즘은 아직 없다.

수론을 연구하는 Taylor는 다음과 같은 새로운 인수분해 문제를 만들었다.

소수 $p$와 두 정수 $a_0, a_1 \in \{0, 1, \ldots, p - 1\}$이 주어진다. $a_0 \equiv b_0 \cdot b_1 \pmod{p}$이고 $a_1 \equiv b_0 + b_1 \pmod{p}$인 두 정수 $b_0, b_1 \in \{0, 1, \ldots, p - 1\}$을 찾아라.

"이 인수분해는 효율적으로 계산할 수 있다는 점에서 훨씬 멋지다"라고 Taylor는 말했다. 이제 그는 여러분을 이 새로운 형태의 인수분해에 초대한다.

첫째 줄에는 테스트 케이스의 수를 나타내는 정수 $1 \le T \le 100$이 주어진다. 각 테스트 케이스마다 한 줄에 공백 하나로 구분된 세 개의 음이 아닌 정수 $p, a_0, a_1$이 주어진다.

각 테스트 케이스마다 한 줄에 $b_0$과 $b_1$이 주어진 두 식을 만족하면 $b_0$과 $b_1$을 오름차순으로 공백 하나로 구분하여 출력한다. 해가 여러 개라면 그중 아무거나 출력해도 된다. 해가 없으면 $-1$을 출력한다.

• $1 \le T \le 100$
• $1 < p < 2^{31}$이고 $p$는 소수다.
• $a_0, a_1 \in \{0, 1, \ldots, p - 1\}$.