Problem F: 计算器

Problem F: 计算器

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

你被要求设计一个计算器完成以下三项任务:

  1. 给定 y, z, p ,计算 y^z mod p 的值;
  2. 给定 y, z, p ,计算满足 x × y ≡ z (mod p)的最小非负整数 x;
  3. 给定 y, z, p ,计算满足 y^x ≡ z (mod p的最小非负整数 x。

Input

输入包含多组数据。

第一行包含两个正整数 T,K  分别表示数据组数和询问类型(对于一个测试点内的所有数据,询问类型相同);
以下 T 行每行包含三个正整数 y, z, p,描述一个询问。

Output

对于每个询问,输出一行答案。

对于询问类型 2 和 3,如果不存在满足条件的,则输出 Orz, I cannot find x!,注意逗号与 I 之间有一个空格。

Sample Input Copy

样例1:
3 1
2 1 3
2 2 3
2 3 3

样例2:
3 2
2 1 3
2 2 3
2 3 3

Sample Output Copy

样例1:
2
1
2

样例2:
2
1
0

HINT

对于全部数据,1 ≤ y, z, p ≤10^9 ,1 ≤ T ≤ 10 且保证 p为质数。