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

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?

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$.

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

Input | Output |
---|---|

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.

67% Solution Ratio

RAB_27Earliest,

LUMBERJACK_MANFastest, 0.2s

pathanLightest, 7.4 MB

Deshi_TouristShortest, 1122B

Login to submit

Prerequisites: Prefix Function/ Z-Function Explanation: Let, first of all, we are asked to find the ...