Practice on Toph

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

Without Any Legend

By Ishtiaq · Limits 1s, 512 MB

You have two arrays A1,A2,...,ANA_1, A_2, ..., A_N and C1,C2,...,CNC_1, C_2, ..., C_N of length NN. Initially for each integer ii (1iN)(1 \leq i \leq N), Ci=AiC_i = A_i.

Now, you are given another array B1,B2,...,BMB_1, B_2, ..., B_M of length MM and you are asked to count the number of segments in array CC where array BB completely overlaps. More formally, array BB will completely overlap along with a segment of array CC if there is a segment [i,j]\left[i, j\right] in array CC where, (j – i+1)=M\left(j\ –\ i+1\right) = M and Ci=B1,C_i = B_1, Ci+1=B2,...,C_{i+1} = B_2, ..., Cj=BMC_j = B_M.

Before start counting you can do an operation as many times as you wish to maximize the number of segments where array BB completely overlaps. The operation is –

  • Choose an integer ii (1iN)(1 \leq i \leq N), then make Ci=Ci+AiC_i = C_i + A_i.

Input

The first line contains an integer TT (1T5)\left(1 \leq T \leq 5\right) – number of test cases.

Each test case contains four lines.

The first line of each test case contains an integer NN (1N104)\left(1 \leq N \leq 10^4\right).

Next line contains NN integers A1,A2,...,ANA_1, A_2, ..., A_N (1Ai106)\left(1 \leq A_i \leq 10^6\right).

Next line contains an integer MM (1M100)\left(1 \leq M \leq 100\right).

The last line of each test case contains MM integers B1,B2,...,BMB_1, B_2, ..., B_M (1Bi106)\left(1 \leq B_i \leq 10^6\right).

Output

The maximum number of segments in array CC where array BB completely overlaps.

Sample

InputOutput
2
4
2 3 2 3
2
6 6
6
2 3 5 2 5 2
3
10 15 10
3
2

For 1st test case —

Initially, C=[2,3,2,3]C = \left[2, 3, 2, 3\right]

Choose i=1,C1=C1+A1=2+2=4i = 1, C_1 = C_1 + A_1 = 2 + 2 = 4

Choose i=1,C1=C1+A1=4+2=6i = 1, C_1 = C_1 + A_1 = 4 + 2 = 6

Choose i=4,C4=C4+A4=3+3=6i = 4, C_4 = C_4 + A_4 = 3 + 3 = 6

Choose i=3,C3=C3+A3=2+2=4i = 3, C_3 = C_3 + A_3 = 2 + 2 = 4

Choosei=2,C2=C2+A2=3+3=6 i = 2, C_2 = C_2 + A_2 = 3 + 3 = 6

Choose i=3,C3=C3+A3=4+2=6i = 3, C_3 = C_3 + A_3 = 4 + 2 = 6

After performing the operations, C=[6,6,6,6]C = \left[6, 6, 6, 6\right].

So, there are three segments [1,2],[2,3][1, 2], [2, 3] and [3,4][3, 4] in array CC where array BB completely
overlaps. No other construction can make more than three segments.

Discussion

Statistics


33% Solution Ratio

c_sharpminorEarliest, 3w ago

mumith_fahim99Fastest, 0.0s

sakib_muhitLightest, 4.7 MB

sakib_muhitShortest, 930B

Submit

Login to submit

Editorial

First of all, think when will an element of BBB will match with an element of CCC? An element CiC_iC...