#include #include #include #include #include #include #include constexpr intmax_t operator ""_jd(unsigned long long n) { return n; } constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; } constexpr size_t operator ""_zu(unsigned long long n) { return n; } // constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; } namespace bit { template int log2p1(Tp n) { if (n == 0) return 0; return (CHAR_BIT * sizeof(long long)) - __builtin_clzll(n); } template Tp ceil2(Tp n) { if (n == 0) return 1; return Tp{1} << log2p1(n-1); } template int ctz(Tp n) { return __builtin_ctzll(n); } } // bit:: template class modint { // FIXME to implement with Montgomery multiplication public: using value_type = typename std::make_signed::type; private: static constexpr value_type S_mod = Modulo; value_type M_value = 0; value_type M_mod; // runtime value (used if S_mod == 0) static constexpr value_type S_inv(value_type n, value_type m) { value_type x = 0; value_type y = 1; value_type a = n; value_type b = m; for (value_type u = y, v = x; a;) { value_type q = b / a; std::swap(x -= q*u, u); std::swap(y -= q*v, v); std::swap(b -= q*a, a); } if ((x %= m) < 0) x += m; return x; } static value_type S_normalize(value_type n, value_type m) { if (n >= m) { n %= m; } else if (n < 0) { n %= m; n += m; } return n; } public: modint() = default; modint(modint const&) = default; modint(modint&&) = default; template 0), Up>::type* = nullptr> modint(value_type n): M_value(S_normalize(n, Modulo)) {} template ::type* = nullptr> modint(value_type n, value_type m): M_value(S_normalize(n, m)), M_mod(m) {} // copying mod modint(modint const& base, value_type n): M_value(S_normalize(n, base.modulo())), M_mod(base.M_mod) {} modint& operator =(modint const&) = default; modint& operator =(modint&&) = default; modint& operator =(value_type n) { M_value = S_normalize(n, modulo()); return *this; } modint& operator +=(modint const& other) { if ((M_value += other.M_value) >= modulo()) M_value -= modulo(); return *this; } modint& operator -=(modint const& other) { if ((M_value -= other.M_value) < 0) M_value += modulo(); return *this; } modint& operator *=(modint const& other) { (M_value *= other.M_value) %= modulo(); return *this; } modint& operator /=(modint const& other) { (M_value *= S_inv(other.M_value, modulo())) %= modulo(); return *this; } modint& operator +=(value_type const& n) { if ((M_value += S_normalize(n, modulo())) >= modulo()) M_value -= modulo(); return *this; } modint& operator -=(value_type const& n) { if ((M_value -= S_normalize(n, modulo())) < 0) M_value += modulo(); return *this; } modint& operator *=(value_type const& n) { (M_value *= S_normalize(n, modulo())) %= modulo(); return *this; } modint& operator /=(value_type const& n) { (M_value *= S_inv(S_normalize(n, modulo()), modulo())) %= modulo(); return *this; } modint operator +(modint const& other) const { return modint(*this) += other; } modint operator -(modint const& other) const { return modint(*this) -= other; } modint operator *(modint const& other) const { return modint(*this) *= other; } modint operator /(modint const& other) const { return modint(*this) /= other; } modint operator +(value_type const& n) const { return modint(*this) += n; } modint operator -(value_type const& n) const { return modint(*this) -= n; } modint operator *(value_type const& n) const { return modint(*this) *= n; } modint operator /(value_type const& n) const { return modint(*this) /= n; } modint operator +() const { return *this; } modint operator -() const { if (M_value == 0) return *this; return modint(*this, modulo()-M_value); } modint pow(intmax_t iexp) const { modint res(*this, 1); for (modint dbl = *this; iexp; iexp >>= 1) { if (iexp & 1) res *= dbl; dbl *= dbl; } return res; } modint& pow_eq(intmax_t iexp) { return *this = this->pow(iexp); } bool operator ==(modint const& other) const { return M_value == other.M_value; } bool operator ==(value_type const& n) const { return M_value == S_normalize(n, modulo()); } bool operator !=(modint const& other) const { return !(*this == other); } bool operator !=(value_type const& n) const { return !(*this == n); } value_type get() const { return M_value; } value_type modulo() const { return ((S_mod > 0)? S_mod: M_mod); } static value_type generator(value_type p) { if (p == 998244353) return 3; return -1; } std::vector sqrt() const { if (*this == 0) return {*this}; intmax_t const p = modulo(); if (p % 4 == 3) { modint r = pow((p+1) / 4); if (r * r == *this) return {r, -r}; return {}; } value_type s = bit::ctz(p-1); value_type q = (p-1) >> s; modint z; for (value_type z0 = 2; z0 < p; ++z0) { z = modint(*this, z0); if (z.pow((p-1) / 2) == -1) break; } value_type m = s; modint c = z.pow(q); modint t = this->pow(q); modint r = this->pow((q+1) / 2); while (true) { if (t == 0) return {modint(*this, 0)}; if (t == 1) return {r, -r}; value_type i = 0; for (auto tt = t; tt != 1; ++i) tt *= tt; if (i == m) return {}; auto b = c; for (value_type j = 0; j < m-i-1; ++j) b *= b; m = i; c = b * b; t *= c; r *= b; } } }; template modint operator +(T1 const& lhs, modint const& rhs) { return rhs + lhs; } template modint operator -(T1 const& lhs, modint const& rhs) { return -(rhs - lhs); } template modint operator *(T1 const& lhs, modint const& rhs) { return rhs * lhs; } template modint operator /(T1 const& lhs, modint const& rhs) { return modint(rhs, lhs) / rhs; } template bool operator ==(T1 const& lhs, modint const& rhs) { return rhs == lhs; } template bool operator !=(T1 const& lhs, modint const& rhs) { return !(lhs == rhs); } // constexpr intmax_t mod = 1'000'000'007; // ' // constexpr intmax_t mod = 998244353; using mi = modint; int main() { intmax_t p; scanf("%jd %*d", &p); int q; scanf("%d", &q); for (int i = 0; i < q; ++i) { intmax_t ra, rb, rc; scanf("%jd %jd %jd", &ra, &rb, &rc); mi a(ra, p); mi b(rb, p); mi c(rc, p); // x = (-b + Sqrt(b*b-4*a*c)) / (2a) auto ds = (b*b-4*a*c).sqrt(); if (ds.empty()) { puts("-1"); continue; } std::vector res; for (auto d: ds) { auto x = (-b+d) / (2*a); res.push_back(x.get()); } std::sort(res.begin(), res.end()); for (size_t i = 0; i < res.size(); ++i) printf("%jd%c", res[i], i+1