Рассмотрим слово w, состоящее из n символов. Мы можем разбить его в точке i (1 ≤ i ≤ n − 1) на префикс p длины i и суффикс s длины n − i. Локальным корнем слова w в точке i называется такое непустое слово r, что:

• p является суффиксом r, или r является суффиксом p, или r равно p;
• s является префиксом r, или r является префиксом s, или r равно s;
• r имеет минимально возможную длину.

Ваша задача — найти точку разбиения слова w, в которой длина локального корня максимальна.

В единственной строке записано слово w, состоящее из строчных латинских букв. Его длина не меньше двух и не больше 300 000 символов.

Выведите через пробел два числа — точку критического разбиения слова w и длину его локального корня в этой точке. Если возможных ответов несколько, выведите любой.

Локальные корни слова «aababaaa» в различных точках:

Точка	1	2	3	4	5	6	7
Локальный корень	a	babaa	ab	ba	aaabab	a	a