Dragon Boat

Dragon boat racing is a team sport, and the performance of each team depends on the abilities of its individual members. However, dragon boat racing also emphasizes coordination, so the performance of a team is evaluated by the value $c = (b_1 * b_2 * \dots * b_m) / (a_1 * a_2 * \dots * a_m)$, where $b_i$ represents the standard ability of the $i$-th member in the team, and $a_i$ represents the ability of the $i$-th member in the team. After simplifying the fraction, we get $c = B/A$, where $\gcd(B, A) = 1$, and $A, B$ are coprime.

However, the situation is different during a competition. We consider the performance under a pressure $M$. The final performance of the team is defined as $C \equiv B/A \pmod M$. We define $1/x = y$ such that $xy \equiv 1 \pmod M$, where $y$ is greater than or equal to 0 and less than $M$. If such a $y$ does not exist, we say the team performs poorly (if $x$ does not have a modular multiplicative inverse modulo $M$). Now, given the competition arrangements for this season, the organizing committee wants to know the performance of each team in the competition.

Input

The first line contains three integers $n, m, k$, representing $n$ teams, each team consisting of $m$ members, and $k$ competitions.

The second line contains $m$ integers, where the $i$-th integer represents the standard ability $b_i$ of the $i$-th position.

From the 3rd line to the $n+2$-th line, there are $n$ lines, each containing $m$ integers. The $j$-th integer in the $(2+i)$-th line represents the ability of the $j$-th member of the $i$-th team.

From the $n+3$-th line to the $n+k+2$-th line, there are $k$ lines, each containing two integers $x, M$, representing that the $x$-th team competes under pressure $M$.

Output

There are $k$ lines, where the $i$-th line represents the performance $C$ of the $i$-th competition arrangement. If the team performs poorly, output "-1".

Examples

Input 1

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

Output 1

3
-1
4

Constraints

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

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