4891 - [Tjoi2017]龙舟

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

但是由于比赛现场的情况不一样，我们认为在现场压力为M的情况下，队伍最后的表现情况认为是C=1(mod M)我们规定在模M的条件下1/x = y，其中y满足xy=1(mod M)并且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行，共n行，每行有两个数x,M，分别表示第x支队伍 会在压力为M的比赛中出战

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

对于20%的数据，1 < M,ai,bi< 10^8,m<=100

对于100%的数据，1 < M,ai,bi< 2*10^8,m<=10000,n<=20,k<=50