Find All Runs in a String

A run in a string S is defined as a triple \((i,j,p)\) satisfying that:

• The substring \(S[i\ldots j]\) has minimum period \(p\). That is, \(p\) is the smallest positive integer such that for all \(k = i, i+1, \ldots, j-p\), we have \(S[k] = S[k+p]\).
• The length of the substring is at least \(2p\), i.e. \(j-i+1 \ge 2p\).
• Left maximal: Either \(i=1\) or \(S[i-1] \neq S[i-1+p]\).
• Right maximal: Either \(j=|S|\) or \(S[j+1] \neq S[j+1-p]\).

Given a string \(S\), your task is to find all its runs. Output the number of runs followed by each run as a triple \((i, j, p)\) on a separate line. (Note: The indices are 1-indexed.)

inputFormat

The input consists of a single line containing the string S.

outputFormat

On the first line, output an integer k representing the number of runs. Then output k lines, each line containing three space‐separated integers: i, j, and p, representing a run \((i,j,p)\).

sample

aaa

1
1 3 1