背景

    期中考前,LH神犇在机房看到kAc神犇SDOI 2013 Round1 Day1出了一道随机数生成器,大喊一声:“这题我和我同桌XJS讨论过!”

    但是他觉得那题的递推式Xi+1 =a*Xi +b太水了,直接令Yi =Xi+b/(a-1),那么得出Yi+1 =aYi ,那么所求跟SDOI 2011计算器的第3小问一样了。

    期中考的那场萌萌的数学考试中,LH神犇在放弃2分提前交卷后(他想148分差不多了),YY出了这道题。

描述

    给出递推公式:Xi+n =(a1Xi+n-1 +a2 Xi+n-2 +……+an Xi +b)% p其中 % p表示除以p的余数(Pascal中的mod p),a1 ,a2 ,…,a,b ,X1 ,X2 ,…Xn是给定的非负整数(ai >=1(1<=i<=n)),LH神犇想知道,对于一组给定的ai,Xi (1<=i<=n)和b,满足Xj+k-1 =Yk (1<=k<=n)的最小正整数的j是多少,或者指出这样的j不存在。

输入格式

输入含多组数据,第一行一个正整数T,表示这个测试点内的数据组数。

接下来T组数据,每组数据第一行有3个正整数p,n,b。

每组数据第二行有n个正整数代表a1 ,a2 ,…,an

每组数据第三行有n个非负整数代表X1 ,X2 ,…Xn

每组数据第四行有n个非负整数代表Y1 ,Y2 ,…Yn

输出格式

共T行,每行一个整数表示满足Xj+k-1 =Yk (1<=k<=n)的最小正整数的j是多少,如果不存在输出-1。

样例输入

3

11 1 2

3

1

3

11 1 6

3

1

6

3 2 2

2 2

2 1

2 2

样例输出

-1

4

3

数据范围与约定

对于20%的测试数据,n=1,p<=106

对于40%的测试数据,n=1,p<=109

对于100%的测试数据,1<=n<=5,0<=Xi,Yi<p(1<=i<=n),0<ai<p(1<=i<=n),0<=b<p,2<=p<=109,保证p是质数并且pn <=109,T<=3。

样例解释

第一组数据,X1 =1,X2 =5,X3 =6,X4 =9,X5 =7,X6 =1,……。不会出现3,所以答案为-1。

第二组数据,X1 =1,X2 =9,X3 =0,X4 =6,所以答案为4。

第三组数据,X1 =2,X2 =1,X3 =2,X4 =2,所以答案为3。

来源

改编自SDOI 2013 Round1 Day1 随机数生成器。