Problem E
Modular Arithmetic

Input

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

Then follow $t$ operations to perform, each of the form $x\text{op}y$. Here, $0\le x,y<n$ are integers, and op is one of ’$+$’, ’$-$’, ’$\ast$’, ’$/$’, indicating an operation to perform. Division, $x/y$ is defined to be $x{y}^{-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