Description

Define a run in a string $S$ of length $|S|$ as a periodic substring that cannot be extended on either side, and whose period appears at least twice completely.

More precisely, a run is a triple $(i, j, p)$ such that $p$ is the minimal period of $S[i..j]$, $j - i + 1 \ge 2p$, and the following two conditions hold:

• 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 runs in it.

Input Format

One line containing a string $S$, guaranteed to consist only of lowercase letters.

Output Format

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

The next $m$ lines each contain three integers describing a run:

• The position of the first character of this run.
• The position of the last character of this run.
• The length of the minimal period of this run.

You should sort all runs by the position of the first character as the primary key, and the position of the last character as the secondary key.

aababaababb

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

Hint

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

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

Translated by ChatGPT 5