Background

Description

Jialidun University has a dragon boat club with $n$ teams, each consisting of $m$ paddlers. Dragon boat racing is a team sport, and while it depends on each individual’s ability, coordination is crucial. Therefore, the ability of a team is evaluated by the value $C=\frac{b_1 \times b_2 \times \cdots \times b_m}{a_1 \times a_2 \times \cdots \times a_m}$, where $b_i$ is the standard ability value for position $i$, and $a_i$ is the ability value of the paddler in position $i$ in the team. After cancellation, we obtain $C=\frac{B}{A}$ with $\gcd(B,A)=1$, i.e., $A$ and $B$ are coprime.

However, due to varying conditions at the venue, we consider that under pressure $M$, the team’s final performance is $C^{-1} \bmod M$. We define that under modulo $M$, $\frac{1}{x}=y$, where $y$ satisfies $xy \equiv 1\pmod M$ and $0 \le y < M$. If no such $y$ exists, we say the team will underperform under pressure $M$ (that is, $y$ is the modular inverse of $x$ modulo $M$; if the inverse does not exist, the team underperforms). Given this season’s schedule, the coaching staff wants to know each team’s performance in the matches.

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