A run in a string $S$ is defined as a periodic substring that cannot be extended to the left or right, and whose period appears at least twice.

Formally, a run is a triple $(i, j, p)$ such that $p$ is the smallest period of $S[i..j]$, $j-i+1 \ge 2p$, and the following two conditions are satisfied:

• Either $i=1$, or $S[i-1] \ne S[i-1+p]$;
• Either $j=n$, or $S[j+1] \ne S[j+1-p]$.

Given a string $S$, find all its runs.

Input

A single line containing the string $S$, which is guaranteed to consist only of lowercase letters.

Output

The first line contains an integer $m$, representing the number of runs.

The next $m$ lines each contain three integers $i, j, p$ describing a run.

You should sort all runs primarily by the starting position $i$ and secondarily by the ending position $j$.

Examples

Input 1

aababaababb

Output 1

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

Subtasks

For $60\%$ of the data, $|S| \le 2 \times 10^5$.

For $100\%$ of the data, $|S| \le 10^6$.