Problem Statement

There are two sequences $X,Y$. The sequence $X$ infinitely repeats the sequence $A$ of length $N$, and the sequence $Y$ infinitely repeats the sequence $B$ of length $M$.

More precisely, the sequence $X$ is constructed from the sequence $A$ as $X=(A_1,A_2,\dots, A_N,A_1,\dots,A_N,A_1,\dots,A_N,\dots)$. The same applies to $Y$.

If there exists a positive integer $i$ satisfying $X_i=Y_i$, output the smallest such integer. If none exists, report so.

Note that the first term of a sequence is term $1$. Also, for a sequence $Z$ and a positive integer $r$, $Z_r$ denotes the $r$-th term of the sequence $Z$.

Constraints

• $1 \leq N,M \leq 5000$
• $1 \leq A_i,B_i \leq 10^4$
• All input values are integers.

Input

The input is given from standard input in the following format.

$N$ $M$
$A_1$ $\dots$ $A_N$
$B_1$ $\dots$ $B_M$

Output

If there exists a positive integer $i$ satisfying $X_i=Y_i$, output the smallest such integer; otherwise, output $-1$. Do not forget the newline at the end.

Sample

2 3
1 2
2 3 3

4

4 1
3 9 1 5
4

-1

10 7
3 4 10 8 19 1 12 39 2 5
8 100 3 38 29 4 11

31