지적 재산권

TDP 주식회사는 JCN 주식회사를 저작권 침해로 고소하기로 했다. 소송을 준비하기 위해 TDP는 JCN의 코드베이스 안에서 침해가 의심되는 구간을 찾아 선정된 언론 관계자들에게 보여 주려 한다. TDP는 기술 인력을 모두 해고한 상태라, 소송에서 이기면 성공 보수를 받는 조건으로 외부 컨설턴트를 고용하려 한다. 당신이 이 자리에 적합하다는 것을 증명하기 위해, 여러 개의 테스트 케이스에 대해 다음 문제를 풀어야 한다.

각 테스트 케이스는 찾아야 할 침해 구간의 개수인 양의 정수 $k$로 시작한다.

그 줄 다음에는 두 개의 코드베이스가 주어진다. 첫 번째 코드베이스는 BEGIN TDP CODEBASE라는 줄로 시작해 여러 줄이 이어진 뒤 END TDP CODEBASE라는 줄로 끝난다. 두 번째 코드베이스는 BEGIN JCN CODEBASE로 시작해 END JCN CODEBASE로 끝난다. END TDP CODEBASE라는 줄은 첫 번째 코드베이스 내부에는 나타나지 않고, END JCN CODEBASE라는 줄은 두 번째 코드베이스 내부에는 나타나지 않는다.

마지막 테스트 케이스 뒤에는 0 하나만 있는 줄이 온다.

각 테스트 케이스마다 다음을 출력한다.

1. CASE n 줄. 여기서 $n$은 테스트 케이스 번호이다(1부터 시작).
2. 최대 $k$개의 침해 구간.

각 구간은 JCN 코드베이스에 나타난 그대로(공백과 줄바꿈 문자 포함) 출력해야 한다. 각 구간 바로 앞에는 다음 줄을 출력한다.

INFRINGING SEGMENT m LENGTH l POSITION p

여기서 $m$은 현재 테스트 케이스 안에서 구간의 순번(1부터 시작), $l$은 구간의 길이(문자 수), $p$는 JCN 코드베이스의 시작으로부터 센 구간의 위치(문자 단위이며, 첫 문자의 위치는 0)이다. 연속한 두 테스트 케이스 사이에는 빈 줄 하나를 출력한다.

코드베이스는 단순히 문자들의 나열이다. 침해 구간이란 JCN 코드베이스 안의 비어 있지 않은 연속된 문자열로서, TDP 코드베이스 안의 어떤 연속된 문자열과 완전히 동일하며, 더 긴 침해 구간에 포함되지 않는 것을 말한다. 공백과 각 줄 끝의 줄바꿈 문자를 포함해 모든 문자를 고려한다.

구간은 길이가 큰 순서대로 정렬한다. 길이가 같은 구간들은 JCN 코드베이스에서 나타나는 위치가 빠른 순서대로 정렬한다. 구간이 $k$개 이하이면 이 순서대로 모두 출력하고, $k$개보다 많으면 앞에서부터 $k$개만 출력한다.

어떤 코드베이스도 50,000자를 넘지 않는다고 가정해도 된다.