Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

New Recruitment

By Ishtiaq · Limits 1s, 256 MB

Mr. Azad applied for a job. During his interview, the interviewer gave him the following task to solve:

Given two arrays $A$ and $B$ consisting of integer numbers, find out the beauty value of each prefix of array $A$. The beauty value for a prefix of $A$ $=$ $($Length of the prefix$)$ $*$ $($Number of segments where that prefix overlaps with array $B$$)$.

Let, $A = [1, 1, 2]$ and $B = [1, 3, 1, 1, 1, 2]$ then for each prefix of $A$ the beauty value is computed as follows:

Beauty of prefix $[1] = 1\cdot 4 = 4$ (Since the length of the prefix $=1$ and $[1]$ overlaps with four different segments of $B$, starting positions of the segments are: $1, 3, 4, 5$)

Beauty of prefix $[1, 1] = 2\cdot 2=4$ (Since the length of the prefix $=2$ and $[1, 1]$ overlaps with two different segments of $B$, starting positions of the segments are: $3, 4$)

Beauty of prefix $[1, 1, 2] = 3\cdot 1=3$ (Since the length of the prefix $=3$ and $[1, 1, 2]$ overlaps with one segment of $B$, starting position of the segment is: $4$)

Since the interview time is very short, the interviewer was only interested in the prefix that has the maximum beauty value. If multiple prefixes had the same beauty value then Mr. Azad had to find the longest prefix that had the maximum beauty value.

Gladly Mr. Azad solved the problem and got the job offer! Can you solve it too?

Input

The first line contains an integer $T (1\leq T\leq 10)$, the number of test cases.

The first line of each test case contains two integers $N, M (1\leq N,M\leq 2\cdot 10^5)$, the number of elements in array $A$ and the number of elements in array $B$ respectively.

The second line of each test case contains $N$ integers $A_1, A_2, …, A_N (1\leq A_i\leq 10^9)$, the elements of array $A$.

The third line of each test case contains $M$ integers $B_1, B_2, …, B_M (1\leq B_i\leq 10^9)$, the elements of array $B$.

Output

For each test case, print the length of the longest prefix having maximum beauty value.

Sample

InputOutput
2
3 6
1 1 2
1 3 1 1 1 2
4 10
3 1 2 5
3 1 2 3 1 2 3 1 2 7

2
3


For the 1st test case $−$

(Explained in the description) prefixes of length $1$ and $2$ have the maximum beauty value but we are interested in maximum prefix length, hence the answer is $2$.

For the 2nd test case $−$

prefix of length $1$ has beauty value $= 1\cdot 3 = 3$

prefix of length $2$ has beauty value $= 2\cdot 3 = 6$

prefix of length $3$ has beauty value $= 3\cdot 3 = 9$

prefix of length $4$ has beauty value $= 4\cdot 0 = 0$

Prefix with length $3$ has the maximum beauty value.

Statistics

67% Solution Ratio

RAB_27Earliest, 1M ago

LUMBERJACK_MANFastest, 0.2s

pathanLightest, 7.4 MB

Deshi_TouristShortest, 1122B