쉬운 그룹 매칭

양의 정수로 이루어진 텍스트 수열 T = t1, t2, ..., tn과 패턴 수열 P = p1, p2, ..., pm이 있다.

일반적인 매칭에서 P가 T의 위치 k에서 매칭된다는 것은 p1 = tk, p2 = t(k+1), ..., pm = t(k+m-1)이 모두 성립한다는 뜻이다. 이런 매칭은 Knuth-Morris-Pratt 알고리즘으로 찾을 수 있다.

여기서는 조금 다른 그룹 매칭을 생각한다. P가 T의 위치 k에서 그룹 매칭된다는 것은 다음 조건을 만족하는 정수열 k = a0 < a1 < ... < am이 존재한다는 뜻이다.

$T_{a_0} + T_{a_0+1} + ... + T_{a_1-1} = p_1$

$T_{a_1} + T_{a_1+1} + ... + T_{a_2-1} = p_2$

...

$T_{a_{m-1}} + T_{a_{m-1}+1} + ... + T_{a_m-1} = p_m$

즉, 텍스트의 위치 k부터 시작해 연속한 원소들을 차례대로 묶었을 때 각 묶음의 합이 패턴의 각 원소와 같아야 한다.

이를테면 T = 1, 2, 1, 1, 3, 2이고 P = 3, 2라면 두 번 그룹 매칭된다. 위치 k = 1에서는 a1 = 3, a2 = 5이고, 위치 k = 5에서는 a1 = 6, a2 = 7이다.

그룹 매칭의 개수는 P가 T의 서로 다른 시작 위치 k에서 그룹 매칭되는 횟수이다.

텍스트 T와 두 패턴 P1, P2가 주어진다. 다음 네 값을 구하여라.

1. T와 P1의 그룹 매칭 개수

2. T와 P2의 그룹 매칭 개수

3. T와 P1 ⋅ n ⋅ P2의 그룹 매칭 개수를 최대로 하는 가장 작은 양의 정수 n. 여기서 n은 원소 하나로 된 수열이고, ⋅는 수열의 이어 붙이기를 뜻한다.

4. 3에서 구한 n에 대해 T와 P1 ⋅ n ⋅ P2의 그룹 매칭 개수

첫째 줄에 테스트 케이스의 개수 C가 주어진다. 테스트 케이스들은 빈 줄로 구분될 수 있다.

각 테스트 케이스는 여섯 줄로 이루어진다.

첫째 줄에는 텍스트의 길이 N이 주어진다.

둘째 줄에는 텍스트의 원소 N개가 주어진다.

셋째 줄에는 첫 번째 패턴의 길이 M1이 주어진다.

넷째 줄에는 첫 번째 패턴의 원소 M1개가 주어진다.

다섯째 줄에는 두 번째 패턴의 길이 M2가 주어진다.

여섯째 줄에는 두 번째 패턴의 원소 M2개가 주어진다.

N <= 5000, M1, M2 <= 600이다. T, P1, P2에 들어 있는 모든 원소의 합은 11,000을 넘지 않는다. 모든 원소는 양의 정수이다.

각 테스트 케이스마다 한 줄에 네 값을 문제에서 요구한 순서대로 공백으로 구분하여 출력한다.

첫 번째 패턴은 텍스트의 위치 1, 2, 7, 8, 9, 10에서 그룹 매칭된다.

두 번째 패턴은 텍스트의 위치 1, 2, 3, 7, 8, 9, 10, 11에서 그룹 매칭된다.

수열 "1, 1, 2, 48, 1, 1, 1"은 텍스트의 위치 1, 2에서 그룹 매칭된다.

1 <= n < 47일 때 수열 "1, 1, 2, n, 1, 1, 1"은 어느 위치에서도 그룹 매칭되지 않는다.

수열 "1, 1, 2, 47, 1, 1, 1"은 텍스트의 위치 2에서만 그룹 매칭된다.

n > 48일 때 세 위치에서 그룹 매칭되는 수열 "1, 1, 2, n, 1, 1, 1"은 없다.