Migrated from Lutece 3237 简单的模板题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

此题不计一血

波波王在数学专题的基础课上讲了数论基础部分，现在他想出个题来检验你听课仔不仔细。

波波王给了你三个数 $y,z,p$ ，他希望你可以实现以下三种操作：

1.计算 $y^z \bmod p$ 的值； 2.计算满足 $xy\equiv z\pmod p$ 的最小非负整数 $x$； 3.计算满足 $y^x\equiv z\pmod p$ 的最小非负整数 $x$；

对于操作2和操作3，如果无论如何也无法找到满足条件的 $x$，请输出"no solution"(去掉引号，注意大小写)。

Input

第一行两个整数 $t,k$，表示操作的数量以及操作的类型。以下所有的操作类型均为 $k$.

接下来 $t$ 行，每行三个整数，分别表示 $y,z,p$.

Output

$t$ 行，每行一个整数，表示答案。

对于操作2和操作3，如果无论如何也无法找到满足条件的 $x$，请输出"no solution"(去掉引号，注意大小写)。

Samples

3 1
2 1 3
2 2 3
2 3 3

2
1
2

3 2
2 1 3
2 2 3
2 3 3

2
1
0

4 3
2 1 3
2 2 3
2 3 3
2 4 3

0
1
no solution
0

Constraints

$1\leq y,z,p\leq 10^9,1\leq t\leq 10,k=\{1,2,3\}$，且 $p$ 为质数。

Resources

2024 UESTC ICPC Training for Math