All Submissions


Statement

Two arrays are given and you have to find whether any permutation of second array is in first array as a subarray(the numbers should be continous) and give the location (index starting from 0). If no such subarray exists output -1.
* Array will contain only 0's and 1's.

Example :

A=[ 0, 1, 0, 0, 1, 1, 0, 1, 0 ]
B=[ 1, 0, 1 ]
Output: 3
So B permutations are : [1,0,1], [0,1,1], [1,1,0] and in the given array A [0,1,1] starts at index 3. Remember if many solutions are possible print the solution with least index.

Input Specifications

First line will contain T - the number of test cases.
For each test case there will be two lines.
K th line will contain N (the number of digits in first array) and then N digits.
K th +1 line will contain M (the number of digits in second array) and then M digits.

Output Specifications

If the subarray exists as per the question, output the index of the first occurrence else output -1 .

Constraints

1 <= T <= 100
1 <= M <= N <= 10000
numbers will be either 0 or 1

Sample Input

2
9 0 1 0 0 1 1 0 1 0
3 1 0 1
9 1 0 0 1 1 1 0 0 1
4 1 1 1 1

Sample Output

3
-1

Problem Setter : Himanshu Shekhar
Problem Tester : Shradha Chhaparia

Languages: Brain,C,C++,Java,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0