시간 제한메모리 제한제출정답맞힌 사람정답 비율
30 초 1536 MB5413827.586%

문제

다음과 같이 양수로 이루어진 두 수열이 있다. T=t1,t2,...,tn (텍스트), P=p1,p2,...,pm(패턴).

매칭이란 p1=tk, p2=tk+1, ..., pm=tk+m-1일때, "P는 k에서 T와 매칭된다" 라고 한다. 이러한 매칭은 Knuth-Morris-Pratt 알고리즘으로 찾을 수 있다.

매칭은 쉬우니깐, 조금 더 어려운 매칭을 생각해보자. P가 k에서 T와 매췽된다는 말은 아래와 같은 조건을 만족하는 수열 k=a0 < a1 < ... < am이 있을 때이다.

ta0 + ta0+1 + ... + ta1-1 = p1

ta1 + ta1+1 + ... + ta2-1 = p2

...

tam-1 + tam-1+1 + ... + tam-1 = pm

매췽은 먼저 텍스트를 그룹짓고 그룹 내의 연속된 합을 구한 다음에, 패턴을 찾는 것이다.

예를 들어, T=1,2,1,1,3,2이고, P=3,2일 때를 생각해보자. 이때는 2개의 매췽이 있는데, k=1 (a1=3, a2=5) 일때와 k=5 (a1=6, a2=7)일 때 이다.

매췽의 개수는 P가 k에서 T와 매췽된때 k의 서로 다른 개수이다.

텍스트 P와 두 개의 패턴 P1, P2가 주어졌을 때, 다음을 구하시오.

1. T와 P1의 매췽의 개수

2. T와 P2의 매췽의 개수

3. T와 P1 ⋅ n ⋅ P2의 매췽의 개수를 최대로 하는 가장 작은 양의 정수 n (⋅는 수열을 합치는 것이다)

4. T와 P1 ⋅ n ⋅ P2의 개수 (여기서 n은 3에서 구한 n이다)

입력

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

각 테스트 케이스는 다음과 같이 여섯 줄로 구성되어 있다.

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

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

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

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

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

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

N<=5000, M1,M2<=600, T와 P1, P2에 포함되어 있는 모든 원소를 합한 값은 11,000을 넘지 않는다.

출력

각 테스트케이스이 대해 한 줄에 문제에서 구하라 했던 순서대로 빈 칸을 사이에 두고 출력한다.

예제 입력 1

1

13 
1 1 1 1 1 47 1 1 1 1 1 1 1
3
1 1 2
3
1 1 1

예제 출력 1

6 8 48 2

힌트

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

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

"1,1,2,48,1,1,1"은 텍스트의 위치 1, 2에서 매췽된다.

n이 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"은 없다.