Cho một xâu kí tự S chỉ bao gồm các chữ cái in thường, hãy tìm xâu con liên tiếp chứa các kí tự giống nhau dài nhất, nếu có nhiều xâu con thỏa mãn thì chọn xâu con có thứ tự từ điển lớn nhất.

Input Format

Một dòng duy nhất chứa xâu S, không quá 1000 kí tự.

Constraints

.

Output Format

In ra đáp án đề bài.

Ví dụ:

Dữ liệu vào

gjjjhaavrrr

Dữ liệu ra

rrr