Internet Problem Solving Contest

• Easy input data set – E1
• The whole test data package, RAR, CR+LF newlines
• The whole test data package, ZIP, CR+LF newlines
• The whole test data package, TAR.GZ, LF newlines

Consider two sequences of positive integers: T = t₁,t₂,…,t_n (text) and P = p₁,p₂,…,p_m (pattern). The classical definition says that P matches T at position k if p₁ = t_k, p₂ = t_k+1, …, and p_m = t_k+m−1. One can easily find 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 = a₀ < a₁ < ⋯ < a_m such that:

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 a₁ = 3,a₂ = 5), the other at k = 5 (with a₁ = 6,a₂ = 7).

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

Problem specification

Given a text T and two patterns P₁, P₂ calculate:

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

Input specification

The first line of the input file 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 first 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 m₁ – the length of the first pattern.
∙ The fourth line contains m₁ positive integers – elements of the first pattern.
∙ The fifth line contains the number m₂ – the length of the second pattern.
∙ The sixth line contains m₂ positive integers – elements of the second pattern.

You may assume the following constraints:
In each test case of the easy data set: n ≤ 5000, m₁,m₂ ≤ 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 ⋅ 10⁶, m₁,m₂ ≤ 2 ⋅ 10⁶, and the sum of all elements of T + P1 + P2 does not exceed 22 ⋅ 10⁶.

Output specification

For each test case output a single line.

This line should contain four space-separated numbers as described in problem specification.

Example

The first 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.