We consider two sequences of integers, and , to be similar if there exists a polynomial, , with integer coefficients of a degree such that (where ) for .
Given sequences and , find and print the minimal integer (where ) such that a cyclic shift of on elements (sequence ) is similar to ; if no such exists, print instead.
Input Format
The first line contains two space-separated integers describing the respective values of (the length of the sequences) and (the maximum degree of polynomial).
The second line contains space-separated integers describing the respective values of .
The third line contains space-separated integers describing the respective values of .
Constraints
Output Format
Print an integer, , denoting the minimal appropriate cyclic shift. If no such value exists, print instead.
Sample Input 0
6 0
1 2 1 2 1 2
4 3 4 3 4 3
Sample Output 0
1
Explanation 0
After a cyclic shift of , sequence is and . Thus, we print .
Sample Input 1
4 2
1 10 100 1000
0 0 0 0
Sample Output 1
-1
Explanation 1
Sequence does not change after any cyclic shift and there are no integers , , and such that and , , and . Thus, we print .