Comedi函数

Time Limit: 2000ms

Memory Limit: 65535kb

Description

已知一常N-1维向量A=(a1,a2,a3……an-1),Comedi函数定义如下:Y=f(X),其中X,Y都是N-1维向量,X=(x1,x2,x3……xn-1),Y=(y1,y2,y3……yn-1),并且yi=(xi*ai)%N。称Y=f(X)为一次迭代,Y=f(f(x))为两次迭代……。

现在,给定N(N为奇素数),向量A,以及目标向量Y(y1,y2,y3,……yn-1)。请问向量X=(1,1,1……)是否能够经过有限次迭代得到向量Y?如果可以,请输出最少经过多少次迭代。如果不可能,请输出-1。

Input

共有多组数据,每组数据含有三行,第一行:一个整数N。第二行N-1个整数代表a1,a2……an-1。第三行N-1个整数代表y1,y2……yn-1。第二、三行的整数范围在[1,N-1]。相互之间可能相同。其中n的范围是(1, 30000)               

Output

一个整数,表示最小迭代步数,如果不可能,请输出-1。

Sample Input

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

Sample Output

2
3

Hint

None

Source

None

提交代码