유전 서열 timer 20s memory 2048MB

유전 서열

마거릿(Margaret)은 유전 서열을 연구한다. 그녀는 일반적인 4글자 유전 알파벳을 쓰지 않는 새로운 생명체에서 얻은 두 서열 \mathbf{A}와 \mathbf{B}를 분석하고 있다. 이 생명체의 유전 서열 코드는 편리하게도 26개의 글자를 필요로 하며, 이는 영문 대문자 'A'부터 'Z'로 표현된다.

마거릿은 서열 \mathbf{A}와 \mathbf{B}를 비교하고 싶다. 가장 좋은 방법은 일련의 서열 분석 테스트를 수행하는 것이다. 각 테스트에서는 \mathbf{A}에서 처음 \mathbf{P}개의 글자만을 포함하는 접두사(prefix)를 취하는데, 이를 \mathbf{A}-접두사(\mathbf{A}-prefix)라고 부른다. 각 테스트에서는 또한 \mathbf{B}에서 마지막 \mathbf{S}개의 글자만을 포함하는 접미사(suffix)를 취하는데, 이를 \mathbf{B}-접미사(\mathbf{B}-suffix)라고 부른다. 마거릿은 이제 \mathbf{A}-접두사와 \mathbf{B}-접미사를 비교해야 한다. 부분문자열(substring)은 연속한 글자들로 이루어진 부분수열이다. \mathbf{A}-접두사에서 나온 어떤 부분문자열이 \mathbf{B}-접미사와 일치(match)한다는 것은, \mathbf{B}-접미사가 그 부분문자열로 시작한다는 뜻이다. 즉, 그 부분문자열이 \mathbf{B}-접미사의 접두사(prefix)라는 뜻이다. 테스트의 결과는 \mathbf{B}-접미사와 일치하는 \mathbf{A}-접두사의 부분문자열 중 가장 긴 것의 길이이다.

마거릿은 \mathbf{Q}개의 서열 분석 테스트 묶음(batch)의 결과를 구하는 소프트웨어가 필요하다. 각 테스트는 서로 독립적임에 유의하라. 마거릿은 \mathbf{A}와 \mathbf{B}의 사본을 많이 가지고 있으며, 각 테스트마다 새로운 사본을 사용한다.

입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 문자열 두 개와 정수 하나, 즉 \mathbf{A}, \mathbf{B}, \mathbf{Q}가 주어진 한 줄로 시작한다. 각 테스트 케이스의 마지막에는 \mathbf{Q}줄이 이어지며, i번째 줄에는 정수 두 개 \mathbf{P_i}, \mathbf{S_i}가 주어진다. 이는 i번째 서열 분석 테스트에서 사용할 접두사 길이와 접미사 길이이다.

출력

각 테스트 케이스마다 Case #x: y_1 ~ y_2 ~ \dots ~ y_{\mathbf{Q}} 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y_i는 입력의 i번째 질의에 대한 답이다.

제한

시간 제한: 20초.
메모리 제한: 2 GB.
1 \le \mathbf{T} \le 100.
1 \leq \mathbf{P_i} \leq \mathbf{A}의 길이.
1 \leq \mathbf{S_i} \leq \mathbf{B}의 길이.

Test Set 1 (Visible Verdict)

1 \le \mathbf{A}의 길이 \le 3000.
1 \le \mathbf{B}의 길이 \le 3000.
1 \le \mathbf{Q} \le 3000.

Test Set 2 (Hidden Verdict)

1 \le \mathbf{A}의 길이 \le 10^5.
1 \le \mathbf{B}의 길이 \le 10^5.
모든 테스트 케이스에 대한 \mathbf{A}의 길이 합은 \leq 5 \times 10^5.
모든 테스트 케이스에 대한 \mathbf{B}의 길이 합은 \leq 5 \times 10^5.
1 \le \mathbf{Q} \le 10^5.

예제

3
ABCABAC CABABA 3
3 6
7 6
6 5
BANANA HABANA 2
5 4
5 5
ABC ABD 1
2 1

Case #1: 1 4 3
Case #2: 4 1
Case #3: 0

Sample Case #1에는 테스트가 3개 있다. 첫 번째 테스트에서는 \mathbf{A}의 접두사 ABC와 \mathbf{B}의 전체 접미사 CABABA를 비교한다. 답은 1인데, C가 ABC에 포함된 부분문자열이면서 CABABA의 접두사인 것들 중 가장 길기 때문이다. 두 번째 테스트에서는 ABCABAC을 CABABA와 비교하고, 가장 긴 일치는 CABA이다. 세 번째 테스트에서는 ABCABA를 ABABA와 비교하고, 가장 긴 일치는 ABA이다.

Sample Case #2에는 테스트가 2개 있다. 첫 번째에서는 BANAN을 BANA와 비교하고 가장 긴 일치는 BANA이다. 두 번째에서는 BANAN을 ABANA와 비교하고 가장 긴 일치는 A이다.

Sample Case #3에는 테스트가 1개 있다. 이 테스트에서는 AB를 D와 비교한다. 일치가 없으므로 답은 0이다.