Problem D
Modular Arithmetic

Input

There are several test cases. Each test case begins with a line containing two integers $n, t$, where $1 \leq n \leq 10^{18}$, and $0 \leq t \leq 100$.

Then follow $t$ operations to perform, each of the form $x\ \mbox{op}\ y$. Here, $0 \leq x, y < n$ are integers, and op is one of ’$+$’, ’$-$’, ’$*$’, ’$/$’, indicating an operation to perform. Division, $x / y$ is defined to be $xy^{-1}$.

Input is terminated by a case where $n = 0$ and $t = 0$, which should not be processed.

Output

For each operation in each test case, output the result of performing the indicated operation modulo $n$. If the operations is not possible (e.g. because of division by zero), output $-1$.

1000 3
1 / 999
1 / 998
578 * 178
13 4
7 / 9
9 * 3
0 - 9
10 + 10
0 0

999
-1
884
8
1
4
7