- 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_{1},t_{2},…,t_{n} (text) and P = p_{1},p_{2},…,p_{m} (pattern). The
classical deﬁnition says that P matches T at position k if p_{1} = t_{k}, p_{2} = t_{k+1}, …, and p_{m} = t_{k+m−1}. 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 = a_{0} < a_{1} < ⋯ < a_{m} such that:

t_{a0} + t_{a0+1} + ⋯ + t_{a1−1} | = p_{1} | ||

t_{a1} + t_{a1+1} + ⋯ + t_{a2−1} | = p_{2} | ||

… | |||

t_{am−1} + t_{am−1+1} + ⋯ + t_{am−1} | = p_{m} |

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_{1} = 3,a_{2} = 5), the other at k = 5 (with a_{1} = 6,a_{2} = 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 P_{1}, P_{2} calculate:

- The evil compatibility of T and P
_{1}. - The evil compatibility of T and P
_{2}. - The smallest positive integer n for which the evil compatibility of T and P
_{1}⋅ n ⋅ P_{2}is maximized.

(The symbol ⋅ represents concatenation.) - The evil compatibility of T and P
_{1}⋅ n ⋅ P_{2}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 m_{1} – the length of the ﬁrst pattern.

∙ The fourth line contains m_{1} positive integers – elements of the ﬁrst pattern.

∙ The ﬁfth line contains the number m_{2} – the length of the second pattern.

∙ The sixth line contains m_{2} 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_{1},m_{2} ≤ 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^{6}, m_{1},m_{2} ≤ 2 ⋅ 10^{6}, and the sum of all elements of T + P1 + P2
does not exceed 22 ⋅ 10^{6}.

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

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.