题目描述

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

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

输入格式

第一行输入三个整数 $n,m,k$，表示有 $n$ 支队伍，每支队伍由 $m$ 个人组成，有 $k$ 场比赛。

第二行输入 $m$ 个整数，第 $i$ 个整数表示第 $i$ 个位置的标准能力值为 $b_i$。

第三行到第 $n+2$ 行，共 $n$ 行，每行有 $m$ 个数，第 $2+i$ 行第 $j$ 个数表示第 $i$ 支队伍第 $j$ 个位置划手的能力值。

第 $n+3$ 行到第 $n+k+2$ 行，共 $k$ 行，每行有两个数 $x,M$，分别表示第 $x$ 支队伍会在压力为 $M$ 的比赛中出战。

输出格式

共 $k$ 行，第 $i$ 行表示在第 $i$ 个参赛安排中队伍的现场表现情况 $C$，如果出现队伍发挥失常，输出 -1。

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

3
-1
4

提示

对于 $20\%$ 的数据，$1<M,a_i,b_i<10^8$，$m \le 100$。

对于 $100\%$ 的数据，$1<M,a_i,b_i<2 \times 10^{18}$，$m \le 10000$，$n \le 20$，$k \le 50$。