반복 문자열

밥은 야심 찬 아방가르드 작가다. 그는 띄어쓰기, 문장부호, 대문자 같은 것을 쓰지 않는다. 그래서 그의 이야기는 영어 소문자로만 이루어진 긴 문자열이다. 비평가들은 그가 반복을 좋아한다고 지적했다. 반복이란 같은 부분 문자열이 사이에 다른 문자 없이 두 번 연달아 나타나는 것을 뜻한다. 밥은 길이가 $n$인 최신작 문자열을 $q$곳의 문예지에 투고했다. 편집자들은 모두 그 일부(부분 문자열)를 싣겠다고 했지만, 그 부분 안에서 가장 긴 반복을 찾아 달라는 조건을 붙였다. 편집자들은 이야기가 지루해지지 않도록 그 부분을 잘라낼 예정이다. 밥은 이 질문들에 답하도록 도움이 필요하다.

길이가 $n$인 문자열 $s[1]s[2]\dots s[n]$이 주어졌을 때, $q$개의 질의에 답하라. 각 질의는 $a_i$와 $b_i$로 주어진다. $s[a_i]s[a_i+1]\dots s[b_i]$의 부분 문자열로 $tt$가 나타나는 가장 긴 문자열 $t$의 길이와, 그런 가장 왼쪽 등장이 시작되는 위치를 구하라.

첫째 줄에 두 정수 $n$과 $q$가 주어진다. 둘째 줄에는 길이가 $n$인 문자열 $s$가 주어지며, 모든 문자는 영어 소문자이다. 이어지는 $q$개의 줄에는 각각 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어진다.

$q$개의 줄을 출력한다. $i$번째 줄에는 공백으로 구분된 두 정수 $\ell_i$와 $c_i$를 출력한다. $\ell_i$는 $s[a_i]\dots s[b_i]$의 부분 문자열로 $tt$가 나타나는 가장 긴 $t$의 길이이다. $c_i$는 그 길이의 반복이 시작하는 가장 작은 인덱스이며, $a_i \le c_i$, $c_i + 2\ell_i - 1 \le b_i$, $s[c_i]\dots s[c_i+\ell_i-1] = s[c_i+\ell_i]\dots s[c_i+2\ell_i-1]$을 만족한다. $\ell_i = 0$이면 정의에 따라 $c_i = a_i$이다.

$1 \le n \le 10^6$

$1 \le q \le 100$

각 $i = 1, 2, \dots, q$에 대해 $1 \le a_i \le b_i \le n$

위 예제의 네 질의는 각각 aabaa, cabaabaac, abaac, aca 부분 문자열을 가리킨다. 굵은 부분이 각 질의 결과에 해당하는 부분 문자열로, 인덱스 $c_i$에서 시작하는 길이 $\ell_i$의 문자열이다. 마지막 질의에는 반복이 없으므로 $\ell_4 = 0$이다.