Output Format

Output $k$ lines. For the $i$-th scheduled match, output the team’s on-site performance value $C^{-1} \bmod M$. If the team underperforms (i.e., the inverse does not exist), output -1.

2 3 3
5 2 3
3 2 3
2 3 2
1 4
2 4
1 7

3
-1
4

Hint

For $20\%$ of the testdata, $1<M,a_i,b_i<10^8$, $m \le 100$.

For $100\%$ of the testdata, $1<M,a_i,b_i<2 \times 10^{18}$, $m \le 10000$, $n \le 20$, $k \le 50$.

Translated by ChatGPT 5