Дана непустая строка s, длина которой N не превышает 10⁶. Будем считать, что элементы строки нумеруются от 1 до N.

Для каждой позиции i символа в строке определим Z-блок как наибольшую подстроку, которая начинается в этой позиции и совпадает с некоторым началом всей строки s. Значением Z-функции Z(i) будем считать длину этого Z-блока. (Заметим, что для первой позиции строки  Z-блок совпадает со всей строкой, поэтому Z(1)=N. С другой стороны, если s[i]≠s[1], то Z(i)=0).

Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск по образцу»).

Требуется для всех i от 1 до N вычислить Z(i).

Дана непустая строка, длина которой не превышает 10⁶. Требуется для каждой позиции  символа в строке найти длину наибольшего палиндрома с центром в этом символе. Строка состоит из букв английского алфавита, большие и маленькие буквы считаются различными. Ограничение времени - 1 секунда.

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\)). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).

В одной из клеток находится клад, который и хочет достать Вася. В лабиринте есть \(K\) входов, из которых Вася может начать свой путь.

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