问题 28481 --龙舟

28481: 龙舟

时间限制: 1 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][48690kb]

题目描述

加里敦大学有一个龙舟队,龙舟队有n支队伍,每只队伍有m个划手,龙 舟比赛是一个集体项目,和每个人的能力息息相关,但由于龙舟讲究配合, 所以评价队伍的能力的是一个值c = (b1 ∗ b2 ∗ ... ∗ bm)/(a1 ∗ a2 ∗ ... ∗ am),其 中bi表示第i个位置标准能力值,ai表示在队伍中第i个位置的划手的能力值。最 后通过约分,我们会得到c = B/A,其中gcd(B, A) = 1,即A, B 是互质的, 但是由于比赛现场的情况不一样,我们认为在现场压力为M的情况下,队伍最 后的表现情况认为是C ≡ B/A(modM),我们规定在模M的条件下1/x = y 其 中y满足xy ≡ 1(modM) 并且y 是大于等于0,并且小于M的值,如果不存在这 样的y我们就认为在M的条件下这支队伍会发挥失常(即y是x在模M意义下的逆 元,如果不存在逆元我们认为队伍发挥失常)。现在是这个赛季的比赛安排情 况,现在教练组想知道各队的在比赛中表现情况。 

输入

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

第二行输入m个整数,第i个表示表征第i个位置的标准能力值为bi 

第3行到第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, ai , bi ≤ 108 , m ≤ 100 



对于100%的数据,有1 < M, ai , bi < 2 ∗ 1018, m ≤ 10000, n ≤ 20, k ≤ 50。 

来源

[提交][状态]