시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (추가 시간 없음) 512 MB 2 2 2 100.000%

문제

Integer factorization serves an important role in many cryptography systems. It is about finding two positive integers p and q for a given positive composite number n such that n = pq and 1 < p ≤ q < n. However, it is a well-known NP-intermediate candidate. We still don’t have any algorithm to solve it in polynomial time.

Taylor, a number theorist, created another factorization problem as follows.

Given a prime number p and two integers a0, a1 ∈ {0, 1, . . . p − 1}. Find two integers b0, b1 ∈ {0, 1, . . . p − 1} such that a0 ≡ b0 · b1 (mod p) and a1 ≡ b0 + b1 (mod p).

“This factoring is way much cooler, in the sense that it can be computed efficiently,” said Taylor. Now, he invites you to enjoy this new variant of factorization.

입력

The first line contains an integer 1 ≤ T ≤ 100 indicating the number of test cases. For each test case, there is a line containing three non-negative integers p, a0, a1 separated by a single blank.

출력

For each test case, output a line containing b0 and b1 in ascending order separated by a single blank if b0 and b1 satisfy the equations. If there are multiple solutions, you may output any of them. If there is no solution, output −1.

제한

  • 1 ≤ T ≤ 100
  • 1 < p < 231 and p is a prime number.
  • a0, a1 ∈ {0, 1, . . . , p − 1}.

예제 입력 1

2
2 1 0
2 1 1

예제 출력 1

1 1
-1