2788. sequence

单点时限: 2.0 sec

内存限制: 256 MB

Petya likes sequences. He has an infinite sequence A[] with the following properties:

A[0], A[1], …, A[N-1] are given;

A[i]=(A[i-1]+A[i-2]+…+A[i-N])%10 for all i>=N;

Sequence B[] with length M is a substring of A[] if there is such index P that B[0]=A[P], B[1]=A[P+1], …, B[M-1]=A[P+M-1]. Your task is to find the smallest possible such P. If there is no such index, print -1.

A will contain between 1 and 7 elements, inclusive.

B will contain between 1 and 50 elements, inclusive.

Each element of A will be between 0 and 9, inclusive.

Each element of B will be between 0 and 9, inclusive.

输入格式

The first line of input gives the number of cases, T(1 ≤ T ≤ 50). T test cases follow.

Each test case consists of two integers n (1 <= n <= 7)and m(1 <= m <= 50) which are represent the size of A[] and B[] respectively,and next two lines are about A[] and B[].

输出格式

Print the such P.

样例

Input
3
3 4
1 2 3
0 7 8 5
3 4
1 2 8
7 4 2 3
5 2
1 2 3 4 5
4 5
Output
5
-1
3

14 人解决,24 人已尝试。

26 份提交通过,共有 153 份提交。

6.2 EMB 奖励。

创建: 11 年,2 月前.

修改: 3 年,6 月前.

最后提交: 3 月前.

来源: ECNU 2009 ACM selective trial From TopCoder

题目标签