[SGU511] Fermat's Last Theorem

题目描述

给定正整数 $n$ 和素数 $p$，请找出三个模 $p$ 非零的整数 $x,y,z$，使得

$x^n+y^n\equiv z^n\pmod p$。

也就是说，需要满足 $1\le x,y,z\le p-1$。如果不存在这样的三元组，则输出 -1。

每个测试点包含多组询问，各组询问相互独立。

输入格式

第一行包含一个整数 $t$，表示询问组数，$1\le t\le1000$。

接下来 $t$ 行，每行包含两个整数 $n,p$，满足 $3\le n\le10^6$，$2\le p\le10^6$，并保证 $p$ 为素数。

输出格式

对于每组询问输出一行：

• 若存在解，输出三个整数 $x,y,z$，满足 $1\le x,y,z\le p-1$ 且 $x^n+y^n\equiv z^n\pmod p$；若有多组解，输出任意一组即可；
• 若不存在解，输出一个整数 -1。

样例

样例输入

2
5 41
3 5

样例输出

-1
1 2 4

注意：对于有解的询问，样例输出并不是唯一答案。