Hard Matching

There is a text sequence T = t1, t2, ..., tn and a pattern sequence P = p1, p2, ..., pm, all made of positive integers.

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

Here we define a harder kind of matching. P matches T at position k if there are indices k = a0 < a1 < ... < am satisfying the following conditions.

• t(a0) + t(a0+1) + ... + t(a1-1) = p1
• t(a1) + t(a1+1) + ... + t(a2-1) = p2
• ...
• t(a(m-1)) + t(a(m-1)+1) + ... + t(am-1) = pm

In other words, starting at position k, split the text into consecutive nonempty groups. The group sums must equal the pattern elements in order.

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

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

1. The number of matches of P1 in T
2. The number of matches of P2 in T
3. The smallest positive integer x that maximizes the number of matches of P1 · x · P2 in T. Here x is treated as a length-1 sequence, and · means sequence concatenation.
4. The number of matches of P1 · x · P2 when x is the value found in item 3

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 the text length N.

The second line contains the N elements of the text.

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

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

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

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

N <= 11 * 10^6 and M1, M2 <= 2 * 10^6. In each test case, the sum of all elements contained in T, P1, and P2 does not exceed 22 * 10^6.

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

In the visible test, the first pattern matches at text positions 1, 2, 7, 8, 9, and 10.

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

The sequence 1, 1, 2, 48, 1, 1, 1 matches at text positions 1 and 2.

For 1 <= x < 47, the sequence 1, 1, 2, x, 1, 1, 1 matches nowhere.

The sequence 1, 1, 2, 47, 1, 1, 1 matches only at text position 2.

For x > 48, no sequence 1, 1, 2, x, 1, 1, 1 matches in three places.