Khảo cổ học

Cho một xâu $s$ chỉ gồm các ký tự "a", "b", "c", trong đó không có hai ký tự liên tiếp nào giống nhau.

Hãy tìm một xâu đối xứng (palindrome) $t$ là dãy con của $s$ sao cho độ dài của $t$ không nhỏ hơn $\lfloor |s|/2\rfloor$.

Xâu $t$ là dãy con của $s$ nếu có thể thu được $t$ bằng cách xóa đi một số (có thể bằng $0$ hoặc tất cả) ký tự của $s$. Xâu đối xứng là xâu đọc từ trái sang phải giống hệt đọc từ phải sang trái.

Bạn không cần cực đại hóa độ dài của $t$, chỉ cần thỏa mãn ràng buộc độ dài nói trên. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$.

Dữ liệu ra

In ra một xâu đối xứng $t$ là dãy con của $s$ với $|t|\ge \lfloor |s|/2\rfloor$.

Ràng buộc

• $2\le |s|\le {10}^6$
• $s$ chỉ gồm các ký tự "a", "b", "c".
• Không có hai ký tự liên tiếp nào của $s$ giống nhau.
• Luôn tồn tại đáp án hợp lệ.

Ví dụ