Easy Group Matching

Let T = t1, t2, ..., tn be a text sequence of positive integers, and let P = p1, p2, ..., pm be a pattern sequence.

In ordinary matching, P matches T at position k when p1 = tk, p2 = t(k+1), ..., pm = t(k+m-1). Such matches can be found with the Knuth-Morris-Pratt algorithm.

Now consider a different kind of group matching. P group-matches T at position k if there is an integer sequence k = a0 < a1 < ... < am satisfying the following conditions.

$T_{a_0} + T_{a_0+1} + ... + T_{a_1-1} = p_1$

$T_{a_1} + T_{a_1+1} + ... + T_{a_2-1} = p_2$

...

$T_{a_{m-1}} + T_{a_{m-1}+1} + ... + T_{a_m-1} = p_m$

In other words, starting at position k in the text, split consecutive elements into groups so that the sum of each group equals the corresponding pattern element.

For instance, if T = 1, 2, 1, 1, 3, 2 and P = 3, 2, there are two group matches. At k = 1, a1 = 3 and a2 = 5. At k = 5, a1 = 6 and a2 = 7.

The number of group matches is the number of distinct starting positions k where P group-matches T.

Given a text T and two patterns P1 and P2, compute the following four values.

1. The number of group matches between T and P1.

2. The number of group matches between T and P2.

3. The smallest positive integer n that maximizes the number of group matches between T and P1 ⋅ n ⋅ P2. Here n is a one-element sequence, and ⋅ means concatenation.

4. For the n found in item 3, the number of group matches between T and P1 ⋅ n ⋅ P2.

The first line contains the number of test cases C. Test cases may be separated by blank lines.

Each test case consists of six lines.

The first line contains N, the length of the text.

The second line contains the N elements of the text.

The third line contains M1, the length of the first pattern.

The fourth line contains the M1 elements of the first pattern.

The fifth line contains M2, the length of the second pattern.

The sixth line contains the M2 elements of the second pattern.

N <= 5000 and M1, M2 <= 600. The sum of all elements in T, P1, and P2 is at most 11,000. Every element is a positive integer.

For each test case, print one line containing the four requested values in order, separated by spaces.

The first pattern group-matches the text at positions 1, 2, 7, 8, 9, and 10.

The second pattern group-matches the text at positions 1, 2, 3, 7, 8, 9, 10, and 11.

The sequence "1, 1, 2, 48, 1, 1, 1" group-matches the text at positions 1 and 2.

For 1 <= n < 47, the sequence "1, 1, 2, n, 1, 1, 1" group-matches nowhere.

The sequence "1, 1, 2, 47, 1, 1, 1" group-matches only at position 2.

For n > 48, there is no sequence "1, 1, 2, n, 1, 1, 1" that group-matches at three positions.