Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

Sample Input

2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

Sample Output

6
-1

题意：给两个数组，要找一个最小的K使得a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]

思路：直接套KMP

#include <iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 1000010
int p[MAXN], t[10010];
int Next[MAXN];
int m, n;
void getNext(int* P, int* f)
{
	f[0] = f[1] = 0;
	for (int i = 1; i < n; i++)
	{
		int j = f[i];
		while (j&&P[i] != P[j])
		{
			j = f[j];
		}
		f[i + 1] = P[j] == P[i] ? j + 1 : 0;
	}
}
int KMP(int* T, int* P, int* f)
{
	int cnt = MAXN;
	getNext(P, f);
	int j = 0;
	for (int i = 0; i < m; i++)
	{
		while (j&&P[j] != T[i])j = f[j];
		if (P[j] == T[i])j++;
		if (j == n)
		{
			cnt = min(i - j + 2, cnt);
			break;
		}
	}
	return cnt;
}

int main()
{
	int T;
	while (~scanf("%d", &T))
	{
		while (T--) {		
			scanf("%d %d", &m, &n);
			for(int i=0;i<m;i++){
				scanf("%d", &p[i]);
			}
			for (int i = 0; i < n; i++)
			{
				scanf("%d", &t[i]);
			}
			
			int minn= KMP(p, t, Next);
			if (minn == MAXN)
			{
				printf("-1\n");
			}
			else
			{
				printf("%d\n", minn);
			}
		}
	}
}