Without Any Legend

Ishtiaq Replay of CUET Intra Univ...
Limits 1s, 512 MB

You have two arrays $A_1, A_2, ..., A_N$ and $C_1, C_2, ..., C_N$ of length $N$. Initially for each integer $i$ $(1 \leq i \leq N)$, $C_i = A_i$.

Now, you are given another array $B_1, B_2, ..., B_M$ of length $M$ and you are asked to count the number of segments in array $C$ where array $B$ completely overlaps. More formally, array $B$ will completely overlap along with a segment of array $C$ if there is a segment $\left[i, j\right]$ in array $C$ where, $\left(j\ –\ i+1\right) = M$ and $C_i = B_1,$ $C_{i+1} = B_2, ...,$ $C_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 $B$ completely overlaps. The operation is –

  • Choose an integer $i$ $(1 \leq i \leq N)$, then make $C_i = C_i + A_i$.

Input

The first line contains an integer $T$ $\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 $N$ $\left(1 \leq N \leq 10^4\right)$.

Next line contains $N$ integers $A_1, A_2, ..., A_N$ $\left(1 \leq A_i \leq 10^6\right)$.

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

The last line of each test case contains $M$ integers $B_1, B_2, ..., B_M$ $\left(1 \leq B_i \leq 10^6\right)$.

Output

The maximum number of segments in array $C$ where array $B$ 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 = \left[2, 3, 2, 3\right]$

Choose $i = 1, C_1 = C_1 + A_1 = 2 + 2 = 4$

Choose $i = 1, C_1 = C_1 + A_1 = 4 + 2 = 6$

Choose $i = 4, C_4 = C_4 + A_4 = 3 + 3 = 6$

Choose $i = 3, C_3 = C_3 + A_3 = 2 + 2 = 4$

Choose$ i = 2, C_2 = C_2 + A_2 = 3 + 3 = 6$

Choose $i = 3, C_3 = C_3 + A_3 = 4 + 2 = 6$

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

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

Submit

Login to submit.

Contributors

Statistics

50% Solution Ratio
c_sharpminorEarliest, Mar '21
steinumFastest, 0.0s
steinumLightest, 5.5 kB
Deshi_TouristShortest, 929B
Toph uses cookies. By continuing you agree to our Cookie Policy.