# Internet Problem Solving Contest

## Problem E – Evil matching

Consider two sequences of positive integers: T = t1,t2,,tn (text) and P = p1,p2,,pm (pattern). The classical deﬁnition says that P matches T at position k if p1 = tk, p2 = tk+1, …, and pm = tk+m1. One can easily ﬁnd all positions where P matches T – for example, by using the Knuth-Morris-Pratt algorithm.

Easy is boring. Let’s make it a bit harder. We say that P evil-matches T at position k if there is a sequence of indices k = a0 < a1 < < am such that:

 ta0 + ta0+1 + ⋯ + ta1−1 = p1 ta1 + ta1+1 + ⋯ + ta2−1 = p2 … tam−1 + tam−1+1 + ⋯ + tam−1 = pm

In other words we are allowed to group and sum up consecutive elements of the text together before matching them against the pattern. For example, if we have T = 1,2,1,1,3,2 and P = 3,2, then there are two evil-matches: one at k = 1 (with a1 = 3,a2 = 5), the other at k = 5 (with a1 = 6,a2 = 7).

The evil compatibility of a text T and a pattern P is the number of diﬀerent k such that P evil-matches T at position k.

Problem speciﬁcation

Given a text T and two patterns P1, P2 calculate:

1. The evil compatibility of T and P1.
2. The evil compatibility of T and P2.
3. The smallest positive integer n for which the evil compatibility of T and P1 n P2 is maximized.
(The symbol represents concatenation.)
4. The evil compatibility of T and P1 n P2 for that n.

Input speciﬁcation

The ﬁrst line of the input ﬁle contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of six lines:
The ﬁrst line contains the number n – the length of text.
The second line contains n positive integers – the elements of text.
The third line contains the number m1 – the length of the ﬁrst pattern.
The fourth line contains m1 positive integers – elements of the ﬁrst pattern.
The ﬁfth line contains the number m2 – the length of the second pattern.
The sixth line contains m2 positive integers – elements of the second pattern.

You may assume the following constraints:
In each test case of the easy data set: n 5000, m1,m2 600, and the sum of all elements of T + P1 + P2 does not exceed 11000.
In each test case of the hard data set: n 11 106, m1,m2 2 106, and the sum of all elements of T + P1 + P2 does not exceed 22 106.

Output speciﬁcation

For each test case output a single line.

This line should contain four space-separated numbers as described in problem speciﬁcation.

Example

input
1

13
1 1 1 1 1 47 1 1 1 1 1 1 1
3
1 1 2
3
1 1 1
output
6 8 48 2

The ﬁrst pattern evil-matches the text at positions 1, 2, 7, 8, 9, and 10.
The second pattern evil-matches the text at positions 1, 2, 3, 7, 8, 9, 10, and 11.
The pattern “1,1,2,48,1,1,1” evil-matches the text twice – at position 1 and at position 2.

Note that the value n = 48 is indeed optimal:
If 1 n < 47, the pattern “1,1,2,n,1,1,1” does not evil-match the text at all.
The pattern “1,1,2,47,1,1,1” evil-matches the text only at position 2.
There is clearly no n > 48 such that the pattern “1,1,2,n,1,1,1” evil-matches the text at three positions.