Prologue

*The writer's intended solution takes about 1700 ms in C#, so this may be difficult in LL languages.

Speaking of summer vacation, when I was a child, summer homework meant a huge amount of calculation practice assigned in calculation drill books.
This is something that happened one summer day in a year when, as summer homework, a mountain of quadratic equation exercises had been assigned.

Young kuuso: "I'm really getting tired of solving nothing but quadratic equations day after day."
God: "Then how about this?"
No sooner had a voice been heard from the heavens than the calculation drill book in front of him suddenly began to shine brilliantly.
He closed his eyes against the glare, and when he timidly opened them after a while, there lay the original drill book, seemingly nothing out of the ordinary.

Young kuuso: "What was that light just now? Oh well."
Muttering to himself, he opened the drill book and sensed something unfamiliar and strange there.

(Question) Solve the following quadratic equation.
$X^2 + 2X + 2 \equiv 0$ (mod $5$)

It seems that, by a whim of God, he has been thrown into the world of mod prime.
With as many as 10000 quadratic equations still left, young kuuso fell into utter despair, not knowing what to do.
God: "This is a little bonus, ho ho!"
Before he knew it, young kuuso was holding in his left hand a single number that could be called the key to this world.

Problem Statement

Input

$P$ $R$
$Q$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_Q$ $B_Q$ $C_Q$

All inputs are integers, and each satisfies the following constraints.
$3\le P \le 10^9$
$2\le R \le P-1$
$1\le Q \le 10^4$
$1 \le A_i < P$ , $1 \le i \le Q$
$0 \le B_i < P$ , $1 \le i \le Q$
$0 \le C_i < P$ , $1 \le i \le Q$
$P$ is prime
$R$ is a primitive root modulo $P$
(Note) $x \not\equiv 0$ being a primitive root of a prime $p$ means that it has the property that $ x ^ k \not\equiv 1 \pmod p $ for every $k$ ($1 \le k \le p-2 $).
In other words, it becomes $1$ for the first time when raised to the power $(p-1)$.

Output

Output $Q$ lines. On the $i$-th line, output the solutions of the $i$-th quadratic equation $ A_i X^2 + B_i X + C_i \equiv 0 \pmod P $ on one line.
Solutions must be in the range $0 \le X \le P-1$; if there are multiple solutions, output all of them in ascending order, separated by single-byte spaces.
If no solution exists, output $-1$.
Print a newline at the end.

Sample

5 2
3
1 0 0
1 0 1
1 0 2

0
2 3
-1

5 2
3
1 2 0
1 2 1
1 2 2

0 3
4
1 2