Source: Libre OJ 173

定义一个字符串 $|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。

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| \le 2 \times 10^5$。

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