Cho dãy DNA được biểu diễn bằng xâu ~s~ chỉ chứa các ký tự A, T, G, C. Đặc điểm nổi trội nhất của DNA là xâu con dài nhất xuất hiện ít nhất 2 lần trong xâu ~s~.

Yêu cầu

Cho dãy DNA được biểu diễn bởi xâu ~s~, xuất ra đặc điểm nổi trội của DNA.

Nếu có nhiều xâu con thỏa mãn, xuất ra xâu con có vị trí xuất hiện đầu tiên là trái nhất.

Dữ liệu

Gồm một dòng duy nhất chứa xâu ~s~ ~(|s| ≤ 10^5)~ chỉ gồm các ký tự A, T, G, C.

Kết quả

Gồm 1 dòng duy nhất là xâu con của ~s~ theo yêu cầu đề bài.

Ví dụ

Sample Input 1

ATATA

Sample Output 1

ATA

Giải thích

Trong các xâu con xuất hiện ít nhất 2 lần: A, T, AT, TA, ATA; xâu con ATA có độ dài lớn nhất.

Sample Input 2

ATTAC

Sample Output 2

A

Giải thích

Trong các xâu con xuất hiện ít nhất 2 lần: A, T; xâu con A có độ dài lớn nhất và vị trí xuất hiện đầu tiên của A ở phía trái nhất → A là kết quả bài toán.