Cho xâu ~S~ chỉ gồm các kí tự tiếng Anh in thường (từ 'a' đến 'z'). Hãy tìm xâu con liên tiếp dài nhất không có 2 kí tự liên tiếp giống nhau. Nếu có nhiều xâu con thỏa mãn thì đưa ra xâu con có thứ tự từ điển lớn nhất.

Yêu cầu: Tìm xâu con liên tiếp dài nhất thỏa mãn điều kiện trên và có thứ tự từ điển lớn nhất.

Input

• Một dòng chứa xâu kí tự ~S~ có độ dài không vượt quá ~10^5~.

Output

• Xâu con tìm được.