【模板】Runs

定义一个字符串 $|S|$ 里的一个 run，指其内部一段两侧都不能扩展的**周期子串**，且周期至少完整出现两次。 严格地说，一个 run 是一个 三元组 $(i,j,p)$，满足 $p$ 是 $S[i..j]$ 的最小周期，$j-i+1 \ge 2p$，且满足如下两个条件： + 要么 $i=1$，要么 $S[i-1]\ne S[i-1+p]$； + 要么 $j=n$，要么 $S[j+1] \ne S[j+1-p]$。 给定字符串 $S$，求他的所有 runs。

一行一个字符串 $S$，保证其只由小写字母构成。

第一行一个整数 $m$，表示 runs 的数量。 接下来 $m$ 行，每行三个整数描述一个 runs： + 这个 runs 的第一个字符的位置 + 最后一个字符的位置 + 这个 runs 的最小循环的长度 你应该以第一个字符的位置为第一关键词，最后一个字符的位置为第二关键词对所有的 runs 进行排序。

aababaababb

7
1 2 1
1 10 5
2 6 2
4 9 3
6 7 1
7 10 2
10 11 1

对于 $60\%$ 的数据，$|S| \le 2 \times 10^5$。 对于 $100\%$ 的数据，$|S| \le 10^6$。