Sgame

슈멘 국제 대회가 IATI로 바뀐 지 3주년을 기념하여 주최 측이 새로운 게임을 준비했다. 데니도 이 게임에 참가하기로 했다. 그녀는 게임이 올라와 있는 태블릿 앞으로 갔다. 태블릿에는 길이가 N이고 소문자 라틴 문자로만 이루어진 문자열 w가 있었다.

게임은 Q라운드로 진행된다. 각 라운드에서 플레이어는 길이 m을 정한다. 길이가 m 이상인 모든 부분 문자열 가운데 가장 많이 나타나는 부분 문자열 s를 찾는다. 이 라운드의 점수는 s가 w에서 나타나는 횟수 cnt이다. 게임을 더 흥미롭게 하려고 플레이어는 k ≥ m인 길이 k도 함께 정한다. 찾은 s의 길이는 k를 넘으면 안 된다. 또한 s의 왼쪽이나 오른쪽에 문자를 붙여 길이가 k보다 길면서 cnt 이상 나타나는 문자열을 만들 수 있으면 안 된다. 다시 말해 s의 길이는 m 이상 k 이하이고, 어떤 부분 문자열 t에 대해서든 ts와 st 중 길이가 k보다 긴 문자열은 w에서 cnt번보다 적게 나타나야 한다. 그런 s가 없으면 이 라운드의 점수는 0이다.

start() 함수는 태블릿에 올라온 문자열을 받는다. 그 뒤 심사 프로그램이 두 정수 m과 k를 인자로 round() 함수를 Q번 호출한다. round()는 각 라운드마다 찾는 부분 문자열의 최대 나타남 횟수를 반환하고, 조건을 만족하는 부분 문자열이 없으면 0을 반환한다.

$1 \le N \le 5 \cdot 10^5$

$1 \le Q \le 10^6$