Problems
Містер А та паліндроми
Містер А та паліндроми
Містер Б подарував Містеру А рядок $s$, що складається з маленьких літер латинського алфавіту. Друзі визначили цікавість непорожньої стрічки $t$, як кількість входжень цієї стрічки $t$ в стрічку $s$ помножена на довжину стрічки $t$. Ваше завдання~--- знайти максимальну цікавість серед всіх непорожніх стрічок які є паліндромами.
Паліндромом вважається стрічка що читається однаково з обох сторін.
\InputFile
Перший рядок містить один рядок $s$ $(1\le |s|\le 3\cdot 10^5)$.
\OutputFile
Виведіть одне ціле число~--- максимальну цікавість серед всіх непорожніх стрічок які є паліндромами.
\Note
У першому прикладі паліндром, що складається з однієї літери <<\t{a}>> має чотири входження у рядок $s$, однак найбільшу цікавість має паліндром <<\t{abacaba}>>.
\Scoring
\begin{enumerate}
\item ($8$ балів): $1\le |s|\le 100$;
\item ($15$ балів): $1\le |s|\le 1\,000$;
\item ($24$ бали): $1\le |s|\le 10\,000$;
\item ($26$ балів): $1\le |s|\le 100\,000$;
\item ($27$ балів): без додаткових обмежень.
\end{enumerate}
Input example #1
abacaba
Output example #1
7
Input example #2
www
Output example #2
4