#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define MT make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<; using vi = vector; using vll = vector; /* 逆数 x と modは互いに素でなければならない。 */ int inverse(int x, int mod) { long long a = x, b = mod, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if (u < 0)u += mod; return (int)u; } /* a^k mod pを返す O(lg(n)) n in Z S = {0} ∪ N k in S p in S 検証済み Codeforces 603B Moodular Arithmetic */ int powMod(int a, long long k, int mod) { if (a == 0)return 0; ll res = 1 % mod, b = a; while (k) { if (k & 1)res = res*b%mod; b = b*b%mod; k >>= 1; } return (int)res; } /* 平方剰余記号 O(log(p)) https://ja.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E5%89%B0%E4%BD%99%E3%81%AE%E7%9B%B8%E4%BA%92%E6%B3%95%E5%89%87 */ int quadraticCharacter(int a, int p) { if (a == 0 || p == 2)return 1; return powMod(a, (p - 1) / 2, p) == 1 ? 1 : -1; } /* √a mod p 素数pのもとで√aを求める。存在しない場合は-1を返す p!=2のとき√a = xとするともう一方の解は-xである。(偶奇が違うので異なる) http://pekempey.hatenablog.com/entry/2017/02/03/220150 */ int sqrtMod(int a, int p) { if (a==0 || p == 2) return a; if (quadraticCharacter(a, p) == -1)return -1; long long k = (p + 1) / 2, b = 2, A; while (quadraticCharacter((int)((b*b - a + p) % p), p) == 1)++b; A = (b*b - a + p) % p; using PLL = pair; auto f = [&](PLL &u, PLL v) { PLL r; r.first = (u.first*v.first + u.second*v.second%p*A) % p; r.second = (u.first*v.second + u.second*v.first) % p; u = r; }; PLL z(1, 0), w(b, 1); while (k) { if (k & 1)f(z, w); f(w, w); k >>= 1; } return (int)z.first; } /* ax^2+bx+c=0をZpで解く。(pは素数) ただし、a!=0 解(重複ありうる) (x1, x2)を返す x1 quadraticEquationMod(int a, int b, int c, int p) { pair res; int D = (int)(((1ll * b*b - 4ll * a*c) % p + p) % p); int r = sqrtMod(D, p); if (r == -1)return { -1,-1 }; int den = inverse(2 * a, p); res.first = (int)((1ll * (p - b + r)*den) % p); res.second = (int)((1ll * (p - b + p - r)*den) % p); if (res.first > res.second)swap(res.first, res.second); return res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int P, R, Q; cin >> P >> R >> Q; while (Q--) { int a, b, c; cin >> a >> b >> c; auto ans = quadraticEquationMod(a, b, c, P); if (ans.first == ans.second)cout << ans.first << endl; else cout << ans.first << ' ' << ans.second << endl; } }