시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 0 0 0.000%

문제

다음과 같이 양수로 이루어진 두 수열이 있다. 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

13 
1 1 1 1 1 47 1 1 1 1 1 1 1
3
1 1 2
3
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"은 없다.