/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
正整数 n および，5 以上の素数 p が与えられます．
次の条件をすべて満たす整数の組 (x,y,z) を 1 つ求めてください．
- 1\leq x < y < z \leq p - 1.
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}.
なお，このような組 (x,y,z) は必ず存在することが証明できます．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\leq T\leq 10^5
- 1\leq n\leq 10^9
- p は 5\leq p\leq 10^9 を満たす素数
入力
入力は以下の形式で標準入力から与えられます．
T
\text{case}_1
\vdots
\text{case}_T
各テストケースは以下の形式で与えられます．
n p
出力
T 行出力してください．i 行目には i 番目のテストケースの解を (x,y,z) とするとき，x,y,z をこの順に空白区切りで出力してください．
解が複数存在する場合，どれを出力しても正解となります．
入力例 1
3 1 7 2 7 10 998244353
出力例 1
1 4 6 1 2 5 20380119 21549656 279594297
ひとつめのテストケースについて，
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413
- x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281
であり，6413\equiv 281\pmod{7} なので，条件を満たしていることが確認できます．
Score : 800 points
Problem Statement
You are given a positive integer n, and a prime number p at least 5.
Find a triple of integers (x,y,z) that satisfies all of the following conditions.
- 1\leq x < y < z \leq p - 1.
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}.
It can be proved that such a triple (x,y,z) always exists.
You have T test cases to solve.
Constraints
- 1\leq T\leq 10^5
- 1\leq n\leq 10^9
- p is a prime number satisfying 5\leq p\leq 10^9.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each case is in the following format:
n p
Output
Print T lines. The i-th line should contain x,y,z with spaces in between where (x,y,z) is a solution for the i-th test case.
If multiple solutions exist, you may print any of them.
Sample Input 1
3 1 7 2 7 10 998244353
Sample Output 1
1 4 6 1 2 5 20380119 21549656 279594297
For the first test case:
- (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413, and
- x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281.
We have 6413\equiv 281\pmod{7}, so the conditions are satisfied.