CSES - Longest Palindrome | Xâu đối xứng dài nhất

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
datnvt , Flower_On_Stone , kitsune
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một xâu, nhiệm vụ của bạn là xác định xâu con đổi xứng dài nhất của xâu. Ví dụ, xâu đối xứng dài nhất trong aybabtu là bab.

Input

  • Dòng đầu vào duy nhất chứa một chuỗi độ dài \(n\). Mỗi kí tự là một trong những a - z.

Output

  • In xâu đối xứng dài nhất trong xâu. Nếu có một số đáp án, bạn có thể in bất kỳ đáp án nào trong số đó.

Constraints

  • \(1 \leq n \leq 10^6\)

Example

Test 1

Input

aybabtu

Output

bab

Bình luận