You have a string $*s* = *s*_{1}*s*_{2}...*s*_{|*s*|}$, where $|*s*|$ is the length of string $*s*$, and $*s*_{*i*}$ its $*i*$-th character.

Let's introduce several definitions:

• A substring $*s*[*i*..*j*]$ $(1 ≤ *i* ≤ *j* ≤ |*s*|)$ of string $*s*$ is string $*s*_{*i*}*s*_{*i* + 1}...*s*_{*j*}$.
• The prefix of string $*s*$ of length $*l*$ $(1 ≤ *l* ≤ |*s*|)$ is string $*s*[1..*l*]$.
• The suffix of string $*s*$ of length $*l*$ $(1 ≤ *l* ≤ |*s*|)$ is string $*s*[|*s*| - *l* + 1..|*s*|]$.

Your task is, for any prefix of string $*s*$ which matches a suffix of string $*s*$, print the number of times it occurs in string $*s*$ as a substring.

Input

The single line contains a sequence of characters $*s*_{1}*s*_{2}...*s*_{|*s*|}$ $(1 ≤ |*s*| ≤ 10^{5})$ — string $*s*$. The string only consists of uppercase English letters.

Output

In the first line, print integer $*k*$ $(0 ≤ *k* ≤ |*s*|)$ — the number of prefixes that match a suffix of string $*s*$. Next print $*k*$ lines, in each line print two integers $*l*_{*i*}$ $*c*_{*i*}$. Numbers $*l*_{*i*}$ $*c*_{*i*}$ mean that the prefix of the length $*l*_{*i*}$ matches the suffix of length $*l*_{*i*}$ and occurs in string $*s*$ as a substring $*c*_{*i*}$ times. Print pairs $*l*_{*i*}$ $*c*_{*i*}$ in the order of increasing $*l*_{*i*}$.