C0865 [TJOI2017]龙舟

加里敦大学有一个龙舟队，龙舟队有 $n$ 支队伍，每只队伍有 $m$ 个划手，龙舟比赛是一个集体项目，和每个人的能力息息相关，但由于龙舟讲究配合，所以评价队伍的能力的是一个值 $c = (b_1 \times b_2… \times b_m)/(a_1 \times a_2… \times a_m)$，其中 $b_i$ 表示第 $i$ 个位置标准能力值，$a_i$ 表示在队伍中第 $i$ 个位置的划手的能力值。最后通过约分，我们会得到 $c= B/A$，其中 $\gcd(B,A)=1$，即 $A, B$ 是互质的，

但是由于比赛现场的情况不一样，我们认为在现场压力为 $M$ 的情况下，队伍最后的表现情况认为是 $C=1(\bmod M)$ 我们规定在模 $M$ 的条件下 $1/x = y$，其中 $y$ 满足 $xy=1(\bmod M)$ 并且 $y$ 是大于等于 $0$，并且小于 $M$ 的值，如果不存在这样的 $y$ 我们就认为在 $M$ 的条件下这支队伍会发挥失常（即 $y$ 是 $x$ 在模 $M$ 意义下的逆元，如果不存在逆元我们认为队伍发挥失常）。现在是这个赛季的比赛安排情况，现在教练组想知道各队的在比赛中表现情况。

样例输入 1

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

样例输出 1

3
-1
4