using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; namespace Yukicoder_551 { using ModuloCalculation; using mlong = ModuloCalculation.mlong; class TEST { public static void Main() { Sol mySol = new Sol(); mySol.Solve(); } } class Sol { public void Solve() { var sb = new StringBuilder(); mlong.mod = P; for(int t = 0; t < Q; t++) { mlong a = A[t], b = B[t], c = C[t]; var sqrtD = ModSqrt.GetModSqrt(b * b - 4 * a * c); if(sqrtD.Length == 0) { sb.AppendLine("-1"); } else if(sqrtD.Length == 1) { sb.AppendLine((-b / (2 * a)).ToString()); } else { var alpha = (-b + sqrtD[0]) / (2 * a); var beta = (-b + sqrtD[1]) / (2 * a); long[] ret = new long[] { (long) alpha, (long) beta }; Array.Sort(ret); sb.AppendLine(String.Join(" ", ret)); } } Console.Write(sb.ToString()); } long P, R; int Q; long[] A, B, C; public Sol() { var d = rla(); P = d[0]; R = d[1]; Q = ri(); A = new long[Q]; B = new long[Q]; C = new long[Q]; for(int i = 0; i < Q; i++) { d = rla(); A[i] = d[0]; B[i] = d[1]; C[i] = d[2]; } } static String rs() { return Console.ReadLine(); } static int ri() { return int.Parse(Console.ReadLine()); } static long rl() { return long.Parse(Console.ReadLine()); } static double rd() { return double.Parse(Console.ReadLine()); } static String[] rsa(char sep = ' ') { return Console.ReadLine().Split(sep); } static int[] ria(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); } static long[] rla(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); } static double[] rda(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); } static T[] mka(int n, T ini) { T[] ret = new T[n]; for (int i = 0; i < n; i++) ret[i] = ini; return ret; } static T[][] mka2(int n, int m, T ini) { T[][] ret = new T[n][]; for (int i = 0; i < n; i++) ret[i] = mka(m, ini); return ret; } static T[][][] mka3(int n, int m, int l, T ini) { T[][][] ret = new T[n][][]; for (int i = 0; i < n; i++) ret[i] = mka2(m, l, ini); return ret; } static T[][][][] mka4(int n, int m, int l, int k, T ini) { T[][][][] ret = new T[n][][][]; for (int i = 0; i < n; i++) ret[i] = mka3(m, l, k, ini); return ret; } } namespace ModuloCalculation { class ModSqrt { public static bool IsQuadraticResidue(mlong v) { if (mlong.mod == 2) return true; if (v == 0) return true; return mlong.ModPow(v, (mlong.mod - 1) / 2) == (mlong)1; } public static mlong[] GetModSqrt(mlong v) { if (!IsQuadraticResidue(v)) return new mlong[0]; if (mlong.mod == 2) return new mlong[] { v }; if (v == 0) return new mlong[] { 0 }; if (v == 1) return new mlong[] { 1, -1 }; if (mlong.mod % 4 == 3) { mlong x = mlong.ModPow(v, (mlong.mod + 1) / 4); return new mlong[] { x, -x }; } // Tonelli Shanks // https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm long p = mlong.mod; long Q = p - 1; int S = 0; while (Q % 2 == 0) { S++; Q >>= 1; } mlong z = 2; while (IsQuadraticResidue(z)) z += 1; int M = S; mlong c = mlong.ModPow(z, Q); mlong t = mlong.ModPow(v, Q); mlong R = mlong.ModPow(v, (Q + 1) / 2); mlong ret = 0; while (true) { if (t == 0) { ret = 0; break; } if (t == 1) { ret = R; break; } int i = 1; mlong tt = t * t; while (true) { if (tt == 1) break; tt *= tt; i++; } mlong b = mlong.ModPow(c, (1L << (M - i - 1))); M = i; c = b * b; t = t * c; R = R * b; } return ret * -1 == ret ? new mlong[] { ret } : new mlong[] { ret, -ret }; } } struct mlong { public static long mod = (long)1e9 + 7; long V; public mlong(long _v = 0) { V = _v; } public static mlong operator +(mlong a, mlong b) { var v0 = a.V + b.V; if (v0 >= mod) v0 -= mod; return new mlong(v0); } public static mlong operator -(mlong a, mlong b) { var v0 = mod + a.V - b.V; if (v0 >= mod) v0 -= mod; return new mlong(v0); } public static mlong operator -(mlong b) { var v0 = mod - b.V; if (v0 >= mod) v0 -= mod; return new mlong(v0); } public static mlong operator *(mlong a, mlong b) { var v0 = a.V * b.V; if (v0 >= mod) v0 %= mod; return new mlong(v0); } public static mlong operator /(mlong a, mlong b) { var v0 = a.V * inv(b.V).V; if (v0 >= mod) v0 %= mod; return new mlong(v0); } public static mlong inv(long x) { long a = 0, b = 0, c = 0; ExtGCD(x, mod, ref a, ref b, ref c); return (mlong)((a + mod) % mod); } public static void ExtGCD(long x, long y, ref long a, ref long b, ref long c) { long r0 = x; long r1 = y; long a0 = 1; long a1 = 0; long b0 = 0; long b1 = 1; long q1, r2, a2, b2; while (r1 > 0) { q1 = r0 / r1; r2 = r0 % r1; a2 = a0 - q1 * a1; b2 = b0 - q1 * b1; r0 = r1; r1 = r2; a0 = a1; a1 = a2; b0 = b1; b1 = b2; } c = r0; a = a0; b = b0; } public static mlong ModPow(mlong a, long k) { if (k == 0) return (mlong)1; if (a == 0) return (mlong)0; mlong x = a; mlong ret = 1; while (k > 0) { if (k % 2 == 1) ret *= x; x *= x; k >>= 1; } return ret; } public static bool operator ==(mlong a, mlong b) { return a.Equals(b); } public static bool operator !=(mlong a, mlong b) { return !(a == b); } public override bool Equals(System.Object obj) { if (obj == null) return false; mlong p = (mlong)obj; if ((System.Object)p == null) return false; return p.V == V; } public override int GetHashCode() { return V.GetHashCode(); } public static implicit operator mlong(long n) { long v = n % mod; if (v < 0) v += mod; return new mlong(v); } public static implicit operator mlong(int n) { long v = n % mod; if (v < 0) v += mod; return new mlong(v); } public static explicit operator long(mlong n) { return n.V; } public override String ToString() { return V.ToString(); } } } }