Modular Arithmetic

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.

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$.

Sample Input 1 | Sample 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 |