문제 131
소수 모듈러의 거듭제곱
정수 $A$, $B$, 음이 아닌 정수 $E$, 양의 정수 $P$에 대해 다음 질의를 처리해 보자.
- $1\ A\ E\ P$: $A^E\bmod P$를 구한다.
- $2\ A\ B\ P$: 음이 아닌 정수 $X$ 중 $A^X\equiv B\pmod P$를 만족하는 가장 작은 값을 구한다.
- $3\ A\ P$: 정수 $X$ 중 $0\le X<P$와 $X^2\equiv A\pmod P$를 만족하는 가장 작은 값을 구한다.
$0^0=1$로 정의한다. $2$번과 $3$번 질의에서는 해가 없을 수도 있다.
입력
첫 번째 줄에 질의의 수를 의미하는 정수 $T$가 주어진다. $(1\le T\le100)$
두 번째 줄부터 $T$개의 줄에 걸쳐 질의가 다음 형식 중 하나로 주어진다.
- $1$번 질의: 정수 $1$, $A$, $E$, $P$가 공백으로 구분되어 주어진다. $(-2^{63}\le A\le2^{63}-1; 0\le E\le2^{63}-1; 1\le P\le2^{63}-1)$
- $2$번 질의: 정수 $2$, $A$, $B$, $P$가 공백으로 구분되어 주어진다. $(-2^{63}\le A,B\le2^{63}-1; 2\le P\le10^9+7)$
- $3$번 질의: 정수 $3$, $A$, $P$가 공백으로 구분되어 주어진다. $(-2^{63}\le A\le2^{63}-1; 2\le P\le2^{61}-1)$
$2$번과 $3$번 질의의 $P$는 소수이다. 모든 $2$번 질의에 대한 $\sqrt P$의 합은 $400\,000$ 이하이다.
출력
각 질의의 답을 입력 순서대로 한 줄에 하나씩 출력한다. $2$번 또는 $3$번 질의에서 해가 없으면 $-1$을 출력한다.
예제 입력 1
9 1 -2 3 7 1 0 0 1 2 0 0 17 2 0 1 17 2 3 2 7 2 1 2 7 3 4 7 3 3 7 3 -1 2
예제 출력 1
6 0 1 0 2 -1 2 -1 1