I. Рудольф и ДНК
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

Во время экспедиции в кратер Ун'горо Рудольф и его верный спутник Байер собрали множество интересных образцов ископаемой флоры и фауны. Теперь они занимаются исследованием кода ДНК элементального динозавра в попытках определить гены, послужившие причиной элементальной мутации.

Код ДНК динозавра представляет собой строку, состоящую из n заглавных букв латинского алфавита. Предполагается, что ген элементальной мутации представляет собой максимальную по длине подстроку кода ДНК, повторяющуюся более одного раза.

Помогите Рудольфу написать программу, определяющую ген элементальной мутации.

Входные данные

Ввод содержит строку s (1 ≤ |s| ≤ 105), состоящую из заглавных букв латинского алфавита — код ДНК.

Выходные данные

Если в коде ДНК ген элементальной мутации отсутствует, выведите «NONE» (без кавычек).

В противном случае в первой строке выведите одно целое число — длину гена элементальной мутации.

Во второй строке выведите позиции, начиная с которых в коде ДНК расположен искомый ген. Выведенные позиции должны быть упорядочены по возрастанию, строка индексируется с нуля.

Если максимальную подстроку невозможно определить однозначно, во второй строке выведите позиции всех возможных кандидатов.

Примеры
Входные данные
EXPEDITIONUNGOROEXPEDITION
Выходные данные
10
0 16
Входные данные
ABBA
Выходные данные
1
0 1 2 3
Входные данные
AB
Выходные данные
NONE