#include <bits/stdc++.h> using namespace std; #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) #define thd(t) std::get<2>(t) using ll = long long; template <typename T> T expt(T a, T n, T mod = std::numeric_limits<T>::max()); template <typename T> T inverse(T n, T mod); std::tuple<ll,ll,ll> extgcd(ll a, ll b); ll P, R; map<ll,ll> inv_map, bsgs_map; ll n, alpha; ll table[100000]; vector<tuple<ll,ll,ll>> P1_factors; std::vector<std::tuple<ll,int>> expos(100000); struct llMod{ llMod() = default; llMod(ll n) : n(n) {} llMod(const llMod&) = default; llMod& operator=(const llMod&) = default; operator long long(){return n;} llMod operator+(const llMod& m) const{ return (n + m.n) % P; } llMod operator-() const{ return (P - n) % P; } llMod operator*(const llMod& m) const{ return n * m.n % P; } llMod operator/(const llMod& m) const{ return n * inverse(m.n, P) % P; } llMod operator^(const ll m) const{ return expt(n, m, P); } ll n; }; const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1}; void init(); ll babyStepGiantStep(ll a, ll b, ll p); ll PohligHellmanPrime(llMod h, llMod generator, ll p, ll e); ll PohligHellman(llMod h, llMod generator, std::vector<std::tuple<ll,ll,ll>>& factors); int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cin >> P >> R; init(); ll g, s; tie(g, s, ignore) = extgcd(2ll, P-1); int Q; std::cin >> Q; for(int i=0;i<Q;++i){ ll a, b, c; std::cin >> a >> b >> c; ll D = (b * b - 4ll * a * c) % P; D = D >= 0 ? D : D + P; ll sq; if(D == 0){ sq = 0; }else{ if(bsgs_map.find(D) == bsgs_map.end()){ bsgs_map[D] = PohligHellman((llMod)D, (llMod)R, P1_factors); } ll m = bsgs_map[D]; if(m % g != 0){ std::cout << -1ll << std::endl; continue; } ll t = s * (m / g) % (P - 1); t = t >= 0 ? t : t + (P - 1); sq = expt(R, t, P); } ll den = 2ll * a % P; if(inv_map.find(den) == inv_map.end()){ inv_map[den] = inverse(den, P); } den = inv_map[den]; ll x0 = (-b - sq) * den % P, x1 = (-b + sq) * den % P; x0 = x0 >= 0 ? x0 : x0 + P; x1 = x1 >= 0 ? x1 : x1 + P; if(x0 > x1){swap(x0, x1);} if(x0 == x1){ std::cout << x0 << std::endl; }else{ std::cout << x0 << " " << x1 << std::endl; } } } void init(){ ll _p = P - 1; for(ll i=2;i*i<=_p;++i){ ll e = 0, pe = 1ll; while(_p % i == 0){ ++e; pe *= i; _p /= i; } if(e > 0){P1_factors.emplace_back(i, e, pe);} } if(_p > 1){P1_factors.emplace_back(_p, 1, _p);} } // solve a^n = b (in F_p) ll babyStepGiantStep(ll a, ll b, ll p){ ll n = std::floor(std::sqrt(p)), alpha = expt(a, n, p); for(int i=0;i<n;++i){ expos[i] = std::make_tuple(expt(a, 1ll * i, p), i); } std::sort(expos.begin(), expos.begin() + n); for(int i=0;n*i<p;++i){ ll v = b * inverse(expt(alpha, 1ll * i, p), p) % p; auto it = std::lower_bound(expos.begin(), expos.begin() + n, std::make_tuple(v, 0), [](const auto& lhs, const auto& rhs){return std::get<0>(lhs) < std::get<0>(rhs);}); if(it != expos.begin() + n && std::get<0>(*it) == v){ ll c = n * i + std::get<1>(*it); return c; } } return -1ll; } std::tuple<ll,ll,ll> extgcd(ll a, ll b){ if(b == 0){ return std::make_tuple(a, 1ll, 0ll); } auto s = extgcd(b, a % b); return std::make_tuple(fst(s), thd(s), snd(s)-(a/b)*thd(s)); } template <typename T> T expt(T a, T n, T mod){ T res = 1; while(n){ if(n & 1){res = res * a % mod;} a = a * a % mod; n >>= 1; } return res; } template <typename T> inline T inverse(T n, T mod){ return expt(n, mod-2, mod); } // solve generator^x \equiv h ll PohligHellmanPrime(llMod h, llMod generator, ll p, ll e){ ll x = 0ll; llMod gamma = generator ^ expt(p, e-1); for(ll k=0;k<e;++k){ ll _h = ((llMod)1 / (generator ^ x) * h) ^ expt(p, e-1-k); ll d = babyStepGiantStep(gamma, _h, P); x = x + expt(p, k) * d; } return x; } // solve x \equiv ak (mod nk) (k = 1, 2) // (when gcd(n1, n2) = 1) tuple<ll,ll> chineseRemainder(ll a1, ll n1, ll a2, ll n2){ ll s, t; tie(ignore, s, t) = extgcd(n1, n2); ll pr = n1 * n2, solution = (a2 * s % pr * n1 % pr + a1 * t % pr * n2 % pr) % pr; if(solution < 0){solution += pr;} return std::make_tuple(solution, pr); } ll PohligHellman(llMod h, llMod generator, std::vector<std::tuple<ll,ll,ll>>& factors){ ll n = P - 1; ll x = -1ll, modulo = -1ll; for(const auto& f : factors){ ll q, e, qe; tie(q, e, qe) = f; llMod g = generator ^ (n / qe), _h = h ^ (n / qe); ll a = PohligHellmanPrime(_h, g, q, e); if(x == -1ll){x = a; modulo = qe;} else{ tie(x, modulo) = chineseRemainder(x, modulo, a, qe); } } return x; }