어려운 매칭

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

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

이번에는 조금 더 어려운 매칭을 정의한다. P가 T의 위치 k에서 매칭된다는 것은 다음 조건을 만족하는 인덱스 k = a0 < a1 < ... < am 이 존재한다는 뜻이다.

즉, 텍스트를 연속한 비어 있지 않은 그룹들로 나누었을 때, 각 그룹의 합이 차례대로 패턴의 원소와 같아야 한다.

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

텍스트 T와 두 패턴 P1, P2가 주어질 때 다음 네 값을 구하시오.

P1이 T에서 매칭되는 개수
P2가 T에서 매칭되는 개수
P1 · x · P2가 T에서 매칭되는 개수를 최대로 만드는 가장 작은 양의 정수 x. 여기서 x는 길이 1인 수열로 보고, ·는 수열의 이어 붙이기를 뜻한다.
3에서 구한 x를 사용했을 때 P1 · x · P2가 T에서 매칭되는 개수

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

각 테스트 케이스는 여섯 줄로 구성된다.

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

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

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

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

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

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

N <= 11 * 10^6, M1, M2 <= 2 * 10^6 이다. 한 테스트 케이스에서 T, P1, P2에 포함된 모든 원소의 합은 22 * 10^6을 넘지 않는다.

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

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

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

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

1 <= x < 47이면 수열 1, 1, 2, x, 1, 1, 1은 어디에서도 매칭되지 않는다.

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

x > 48일 때는 세 곳에서 매칭되는 수열 1, 1, 2, x, 1, 1, 1이 없다.