#ifdef LOCAL111 #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #define _USE_MATH_DEFINES #include const int INF = 1e9; using namespace std; template ostream& operator<< (ostream& os, const pair& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; } #define endl '\n' #define ALL(a) (a).begin(),(a).end() #define SZ(a) int((a).size()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #ifdef LOCAL111 #define DEBUG(x) cout<<#x<<": "<<(x)< void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;} #else #define DEBUG(x) true template void dpite(T a, T b){ return; } #endif #define F first #define S second #define SNP string::npos #define WRC(hoge) cout << "Case #" << (hoge)+1 << ": " template void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;} template bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} template bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} typedef long long int LL; typedef unsigned long long ULL; typedef pair P; void ios_init(){ //cout.setf(ios::fixed); //cout.precision(12); #ifdef LOCAL111 return; #endif ios::sync_with_stdio(false); cin.tie(0); } //library using Integer = long long; const Integer mod = 1e9+7; template long long gcd(T x, T y){ return y==0 ? x : gcd(y, x%y); } template long long lcm(T x, T y){ return x/gcd(x,y)*y; } //const int MAX_n = ; //const int MAX_r = ; /*long long Cdp(int n, int r){ if() }*/ //res.first*a+res.second*b == 1 となるresを返す (a,bは互いに素) pair extgcd(Integer a,Integer b) { if(b==1){ return pair(0,1); } pair t=extgcd(b,a%b); return pair(t.second,t.first-a/b*t.second); } //modの逆元を返す Integer inverse(Integer a,Integer modl) { return (extgcd(modl,a).second+modl)%modl; } //xCyを返す long long Cinv(long long x, long long y, const long long modl = mod){ long long n = 1 ,r = 1; for(int i = 0; i < y; i++){ n = n*(i+1)%modl; r = r*(x-i)%modl; } return r*inverse(n,modl)%modl; } long long H(int n, int r){ return Cinv(n+r-1,r); } bool primej(long long x){ if(x == 0 || x == 1) return false; for(long long i = 2; i*i <= x; i++){ if(x%i == 0) return false; } return true; } std::vector eratosthenes(int n){ std::vector res(n+1,true); res[0] = false; res[1] = false; for(long long i = 2; i*i <= n; i++){ for(long long j = 2; i*j <= n; j++){ res[i*j] = false; } } return res; } template unordered_map primeFactorizem(T x){ unordered_map res; for(T i = 2; i*i <= x; i++){ while(x%i == 0){ res[i]++; x /= i; } } if(x != 1) res[x]++; return res; } template vector> primeFactorize(T x){ vector> res; for(T i = 2; i*i <= x; i++){ int cnt = 0; while(x%i == 0){ cnt++; x /= i; } if(cnt != 0) res.emplace_back(i,cnt); } if(x != 1){ if(res.size() != 0 and res.back().first == x){ res.back().first++; }else{ res.emplace_back(x,1); } } return res; } Integer modpow(Integer x, Integer y, Integer mod){ x %= mod; y %= mod; Integer tmp = x; Integer res = 1; while(y != 0){ if(y&1){ res = res*tmp%mod; } tmp = tmp*tmp%mod; y >>= 1; } return res; } // x = second (mod first) 0以上の最小解 Integer garner_gen(const vector>& ex) { int n = ex.size(); Integer res = 0; Integer k = 1; for(int i = 0; i < n; ++i) { Integer x, m; tie(m,x) = ex[i]; x = (x%m+m)%m; Integer g = gcd(k,m); if((x-res)%g != 0) return -1; Integer inv = inverse(k/g,m/g); Integer v = ((x-res)/g%m+m)%m*inv%m; Integer nk = k/g*m; res = (res+v*k%nk)%nk; k = k/g*m; } return res; } Integer garner_gen(const vector& x, const vector& mod){ int n = x.size(); vector> v(n); for(int i = 0; i < n; ++i) { v[i] = {mod[i],x[i]}; } return garner_gen(v); } //あんま検証してないよ Integer garner(const vector>& ex) { int n = ex.size(); Integer res = 0; Integer k = 1; for(int i = 0; i < n; ++i) { Integer x, m; tie(m,x) = ex[i]; // x = (x%m+m)%m; Integer inv = inverse(k,m); Integer v = ((x-res)%m+m)%m*inv%m; res = (res+v*k); k = k*m; } return res; } Integer garner(const vector& x, const vector& mod){ int n = x.size(); vector> v(n); for(int i = 0; i < n; ++i) { v[i] = {mod[i],x[i]}; } return garner(v); } // //検証甘い rand.ccに依存 // bool isPrime_MillerRabin(Integer x, int k = 20){ // if(x == 1) return false; // if((x&1) == 0){ // if(x == 2){ // return true; // }else{ // return false; // } // } // Integer n = x; // Integer s = 0; // x--; // while((x&1) == 0){ // x /= 2; // s++; // } // Integer d = x; // for(int cnt = 0; cnt < k; ++cnt) { // Integer a = randInt((Integer)1,n); // if(modpow(a,d,n) != 1){ // bool f = true; // Integer num = modpow(a,d,n); // for(int r = 0; r < s; ++r) { // if(num == n-1){ // f = false; // break; // } // num = num * num % n; // } // if(f) return false; // } // } // return true; // } //librarys // solve Discrete Logarithm Problem // log_r(a) mod p-1 template class DLP { private: vector> bsteps; unordered_map gsteps; long long root; long long mod; public: DLP(Integer p, Integer r) { mod = p; root = 1; while(root*root <= p) root++; Integer rinv = inverse(r, p); Integer giant_step = modpow(rinv, root, p); Integer baby_step = r; bsteps = vector>(root+1); gsteps = unordered_map(2*root+1); Integer g = 1; Integer b = 1; for(int i = 0; i <= root; ++i) { gsteps[g%p] = i; bsteps[i] = {b%p, i}; g *= giant_step; g %= p; b *= baby_step; b %= p; } } Integer baby_step_giant_step(Integer a) { Integer ainv = inverse(a, mod); for(int i = 0; i <= root; i++) { auto ite = gsteps.find(bsteps[i].first*ainv%mod); if(ite != gsteps.end()) { return (ite->second*root+bsteps[i].second)%(mod-1); } } return -1; } }; int main() { ios_init(); LL p, r; while(cin >> p >> r) { int q; cin >> q; DLP dlp(p, r); REP(_, q) { LL a, b, c; cin >> a >> b >> c; DEBUG(a); DEBUG(b); DEBUG(c); LL s = (b*b%p-4*a*c%p)%p; s = (s+p)%p; DEBUG(s); if(s != 0) { LL log = dlp.baby_step_giant_step(s); DEBUG(log); if(log == -1 or log%2 == 1) { cout << -1 << endl; } else { LL root = modpow(r, log/2, p); set s; s.insert(((-b+root)*inverse(2*a, p)%p+p)%p); s.insert(((-b-root)*inverse(2*a, p)%p+p)%p); pite(ALL(s)); } } else { LL root = 0; set s; s.insert(((-b+root)*inverse(2*a, p)%p+p)%p); s.insert(((-b-root)*inverse(2*a, p)%p+p)%p); pite(ALL(s)); } } } return 0; }