QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 21648. Runs

Statistics

Source: Libre OJ 173

定义一个字符串 |S| 里的一个 run,指其内部一段两侧都不能扩展的周期子串,且周期至少完整出现两次。

严格地说,一个 run 是一个 三元组 (i,j,p),满足 pS[i..j] 的最小周期,ji+12p,且满足如下两个条件:

  • 要么 i=1,要么 S[i1]S[i1+p]
  • 要么 j=n,要么 S[j+1]S[j+1p]

给定字符串 S,求他的所有 runs。

Input

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

Output

第一行一个整数 m,表示 runs 的数量。

接下来 m 行,每行三个整数 i,j,p 描述一个 runs。

你应该以第一个字符的位置为第一关键词,最后一个字符的位置为第二关键词对所有的 runs 进行排序。

Example

Input

aababaababb

Output

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

Scoring

对于 60% 的数据,|S|2×105

对于 100% 的数据,|S|106