Dragon Boat Team Performance

At Garyton University, the dragon boat team competition involves n teams, each consisting of m paddlers. For each team the standard performance value is defined as

\( C = \frac{b_1 \times b_2 \times \cdots \times b_m}{a_1 \times a_2 \times \cdots \times a_m} \)

After fully reducing \(C\) to an irreducible fraction \(\frac{B}{A}\) (so that \(\gcd(B, A)=1\)), the final performance under pressure \(M\) is computed as the modular inverse of \(C\) modulo \(M\). In other words, we define the performance result \(y\) by the equation:

\( \frac{B}{A} \times y \equiv 1 \pmod{M} \)

This is equivalent to solving for \(y\) in the congruence:

\( B\,y \equiv A \pmod{M} \)

If an integer \(y\) with \(0 \le y < M\) exists, then it is taken as the team’s performance; otherwise, if no such \(y\) exists (i.e. when \(B\) does not have an inverse modulo \(M\)), the team is considered to perform abnormally.

Given the competition schedule, determine the performance of each team.

inputFormat

The first line contains three positive integers \(n\), \(m\), and \(M\) separated by spaces, where \(n\) is the number of teams, \(m\) is the number of paddlers in each team, and \(M\) is the pressure modulus.

Then, for each team, there are two lines:

• The first line contains \(m\) integers \(b_1, b_2, \ldots, b_m\) representing the standard ability values at each position.
• The second line contains \(m\) integers \(a_1, a_2, \ldots, a_m\) representing the actual ability values of the paddlers.

outputFormat

For each team, output a single line containing a single integer: the performance value \(y\) (i.e. the modular inverse computed as described) if it exists; otherwise, output -1 if the team performs abnormally.

sample

1 3 11
2 3 5
1 2 3

9