#include #include #include #include intmax_t modpow(intmax_t base, intmax_t iexp, intmax_t mod) { intmax_t res = 1; for (intmax_t dbl = base; iexp; iexp >>= 1) { if (iexp & 1) (res *= dbl) %= mod; (dbl *= dbl) %= mod; } return res; } intmax_t moddiv(intmax_t n, intmax_t d, intmax_t mod) { return n * modpow(d, mod-2, mod) % mod; } std::vector modsqrt(intmax_t n, intmax_t p) { if (p % 4 == 3) { intmax_t r = modpow(n, (p+1)/4, p); if (r*r % p == n) return {r, p-r}; return {}; } intmax_t s = __builtin_ctzll(p-1); intmax_t q = (p-1) >> s; intmax_t z; for (z = 2; z < p; ++z) if (modpow(z, (p-1)/2, p) == p-1) break; intmax_t m = s; intmax_t c = modpow(z, q, p); intmax_t t = modpow(n, q, p); intmax_t r = modpow(n, (q+1)/2, p); while (true) { if (t == 0) return {0}; if (t == 1) return {r, p-r}; intmax_t i = 0; for (intmax_t tt = t; tt != 1; ++i) (tt *= tt) %= p; if (i == m) return {}; intmax_t b = c; for (intmax_t j = 0; j < m-i-1; ++j) (b *= b) %= p; m = i; c = b * b % p; (t *= c) %= p; (r *= b) %= p; } } int main() { intmax_t P, R; size_t Q; scanf("%jd %jd %zu", &P, &R, &Q); for (size_t i = 0; i < Q; ++i) { intmax_t A, B, C; scanf("%jd %jd %jd", &A, &B, &C); // (-b +- sqrt(b*b-4*a*c)) / (2*a) std::set sol; intmax_t S = (B*B - 4*A*C) % P; if (S < 0) S += P; for (intmax_t s: modsqrt(S, P)) { intmax_t n = (s - B) % P; if (n < 0) n += P; intmax_t a = 2*A % P; sol.insert(moddiv(n, a, P)); } if (sol.empty()) { puts("-1"); } else { bool out = false; for (auto x: sol) { printf("%s%jd", out? " ":"", x); out = true; } puts(""); } } }