Cùng với số phận trớ trêu, Nadeko có một xâu $s$ gồm các chữ cái tiếng Anh viết thường. Mong muốn tột cùng của cô là xây dựng một xâu $t$ thỏa mãn các điều kiện sau:
- $t$ không chứa $s$ như một xâu con (không nhất thiết liên tiếp).
- Mọi xâu con của $s$ mà không trùng với $s$ đều được chứa trong $t$ như một xâu con.
Hãy giúp cô ấy tìm xâu $t$ có độ dài nhỏ nhất có thể. Nếu có nhiều xâu như vậy, bạn được phép in ra một xâu bất kỳ.
Dữ liệu vào
Một dòng duy nhất của dữ liệu vào chứa xâu $s$ ($2 \le |s| \le 10^6$) — xâu của Nadeko. Đảm bảo rằng $s$ chỉ chứa các chữ cái viết thường.
Dữ liệu ra
Trên một dòng duy nhất, in ra một xâu $t$ bất kỳ có độ dài nhỏ nhất thỏa mãn các điều kiện của bài toán.
Ví dụ
Dữ liệu vào 1
aaaa
Dữ liệu ra 1
aaa
Dữ liệu vào 2
bba
Dữ liệu ra 2
bab
Ghi chú
Trong ví dụ thứ hai, xâu bab chứa bb, ba, a, b làm các xâu con nhưng không chứa bba. Cũng dễ thấy rằng không thể xây dựng một dãy hợp lệ có độ dài $2$, vì vậy bab là một đáp án hợp lệ.