题目背景

翻译自 CSES-1111 题。

题目描述

给定一个字符串，任务是找出该字符串的最长回文子串。例如，字符串 aybabtu 中的最长回文子串是 bab。

输入格式

输入一行，包含一个由小写字母组成的字符串，长度为 $n$（字符范围 $a–z$）。

输出格式

输出字符串中最长的回文子串。如果有多个解，输出任意一个即可。

样例

aybabtu

bab

说明/提示

$1 \leq n \leq 10^6$。