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+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 = 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.
Given a text T and two patterns P1, P2 calculate:
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.
For each test case output a single line.
This line should contain four space-separated numbers as described in problem speciﬁcation.
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.