我又来了

using namespace std;
long long t,k;
long long y,z,p;
map<long long,long long>mp;
long long ksm(long long x,long long y){
    long long r=1;
    while(y){
        if(y&1){
            r=r*x%p;
        }
        x=x*x%p;
        y>>=1;
    }
    return r;
}
long long bsgs(){
    mp.clear();
    long long m=ceil(sqrt(p));
    long long k=1,l=1;
    for(long long i=1;i<=m;i++){
        k=k*y%p;
        mp[k*z%p]=i;
    }
    for(long long i=1;i<=m;i++){
        l=l*k%p;
        if(mp[l]){
            return i*m-mp[l];
        }
    }
    return -1;
}
long long exgcd(long long a,long long b,long long &x,long long y){
    if(!b){
        x=1;
        y=0;
        return a;
    }else{
        long long r=exgcd(b,a%b,x,y);
        long long t=x;
        x=y;
        y=t-(a/b)*y;
        return r;
    }
}
int main(){
    scanf("%lld%lld",&t,&k);
    if(k==1){
        while(t--){
            scanf("%lld%lld%lld",&y,&z,&p);
            printf("%lld\n",ksm(y,z));
        }
    }else if(k==2){
        while(t--){
            scanf("%lld%lld%lld",&y,&z,&p);
            if(__gcd(y,p)!=1){
                printf("Orz, I cannot find x!\n");
            }else{
                printf("%lld\n",z*ksm(y,p-2)%p);
            }
        }
    }else{
        while(t--){
            scanf("%lld%lld%lld",&y,&z,&p);
            if(y%p==z%p){
                printf("1\n");
                continue;
            }
            long long x=bsgs();
            if(x<=0)printf("Orz, I cannot find x!\n");
            else printf("%lld\n",x);
        }
    }
}

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    for(; k; k >>= 1) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
    }
    return res;
}

inline LL gcd(LL a, LL b) {
    if(!b) return a;
    return gcd(b, a % b);
}

const int MO = 611977, MAXN = 1000005;

struct LinkedHashMap {
    int head[MO + 5], key[MAXN], val[MAXN], nxt[MAXN], tot;
    inline void clear() {
        tot = 0; memset(head, -1, sizeof(head));
    }
    LinkedHashMap() {
        clear();
    }
    inline void insert(int k, int v) {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) {
                val[i] = v; return;
            }
        }
        key[tot] = k; val[tot] = v; nxt[tot] = head[idx]; head[idx] = tot++;
    }
    inline int operator[](const int &k) const {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) return val[i];
        }
        return -1;
    }
} x;

inline LL bsgs(LL a, LL b, LL p) {
    a %= p; b %= p;
    if(a == 0) return b == 0 ? 1 : -1;
    if(b == 1) return 0;
    x.clear(); x.insert(1, 0);
    LL m = ceil(sqrt(p - 1)), inv = fpow(a, p - m - 1, p);
    for(LL i = 1, e = 1; i < m; i++) {
        e = e * a % p;
        if(x[e] == -1) x.insert(e, i);
    }
    for(LL i = 0; i < m; i++) {
        LL res = x[b];
        if(res != -1) return i * m + res;
        b = b * inv % p;
    }
    return -1;
}

int T, K;

int main() {
    T = readint(); K = readint();
    while(T--) {
        LL y = readint(), z = readint(), p = readint();
        if(K == 1) {
            printf("%lld\n", fpow(y, z, p));
        } else if(K == 2) {
            LL g = gcd(y, p);
            if(z % g) puts("Orz, I cannot find x!");
            else printf("%lld\n", fpow(y * fpow(z, p - 2, p) % p, p - 2, p));
        } else {
            LL res = bsgs(y, z, p);
            if(res == -1) puts("Orz, I cannot find x!");
            else printf("%lld\n", res);
        }
    }
    return 0;
}