Contact

Astro Insky 박사는 전파망원경 센터에서 일한다. 최근 그녀는 은하 중심에서 곧바로 전송되는 매우 흥미로운 마이크로파 펄스 신호를 발견했다. 이 신호는 외계 지적 생명체가 보낸 것일까, 아니면 그저 별들의 평범한 맥동에 지나지 않는 것일까?

Insky 박사가 진실을 밝힐 수 있도록, 그녀가 기록한 파일 속 비트 패턴을 분석하는 도구를 만들어 주어야 한다. 박사는 매일의 데이터 파일에서 길이가 $A$ 이상 $B$ 이하인 패턴 중 가장 자주 반복되는 것들을 찾고자 한다. 각 경우에 대해 가장 큰 $N$개의 서로 다른 빈도(즉, 등장 횟수)를 구한다. 패턴의 등장은 서로 겹칠 수 있으며, 최소 한 번 이상 등장하는 패턴만 고려한다.

• 첫째 줄: 패턴의 최소 길이를 나타내는 정수 $A$
• 둘째 줄: 패턴의 최대 길이를 나타내는 정수 $B$
• 셋째 줄: 보고할 서로 다른 빈도의 개수를 나타내는 정수 $N$
• 넷째 줄: 0과 1로 이루어진 문자열이며, 문자 2로 끝난다.

표준 출력으로 최대 $N$개의 줄로 이루어진 보고서를 출력한다. 가장 큰 빈도부터 차례로, 최대 $N$개의 빈도와 그에 해당하는 패턴들을 나열한다. 줄은 빈도가 큰 순서대로 정렬한다. 각 줄은 빈도 패턴 패턴 ... 패턴 형식이며, 여기서 빈도는 뒤따르는 패턴들의 등장 횟수이다. 한 줄 안에서 패턴은 길이가 긴 순서대로 나열하고, 길이가 같은 패턴들은 이진수 값이 큰 순서(역순)로 나열한다. 서로 다른 빈도가 $N$개보다 적으면 출력 줄 수도 $N$보다 적어진다.

• $0 < N \le 20$
• $0 < A \le B \le 20$