loj#P2641. 「TJOI2017」龙舟

「TJOI2017」龙舟

题目描述

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

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

输入格式

第一行输入三个个整数 n,m,kn, m, k,表示有 nn 支队伍,每支队伍有 mm 个人组成,有 kk 场比赛。

第二行输入 mm 个整数,第 ii 个表示表征第 ii 个位置的标准能力值为 bib_i

33 行到第 n+2n + 2 行,共 nn 行,每行有 mm 个数,第 2+i2 + i 行第 jj 个数表示第 ii 支队伍的第 jj 个位置的划手的能力值。

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

输出格式

kk 行,第 ii 行表示在第 ii 个参赛安排种队伍的现场表现情况 CC,如果出现队伍发挥失常,输出 -1

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

数据范围与提示

  • 对于 20%20\% 的数据,1<M,ai,bi<1081 < M, a_i, b_i < 10^8m100m \leq 100
  • 对于 100%100\% 的数据,1<M,ai,bi<2×10181 < M, a_i, b_i < 2 \times 10^{18}m10000m \leq 10000n20n \leq 20k50k \leq 50