런 열거

길이가 $N$인 문자열 $S$이 주어진다. $S$의 런을 열거한다. 즉, 다음 조건을 만족하는 튜플 $(t, l, r)$을 열거한다.

• $S[l..r-1]$의 최소 주기는 $t$이며, $r - l \geq 2t$이 성립한다.
• $l$과 $r$은 최대이다. 즉, $(t, l - 1, r)$과 $(t, l, r + 1)$은 위 조건을 만족하지 않는다.

제약 조건

• $1 \leq N \leq 200,000$
• $S$의 각 문자는 영문 소문자이다.

$S$

$M$
$t_1$ $l_1$ $r_1$
$t_2$ $l_2$ $r_2$
:
$t_M$ $l_M$ $r_M$

여기서 $M$은 런의 개수이며, 런은 $(t, l, r)$ 튜플로 사전순으로 출력한다.