Một xâu con lặp lại là một xâu con xuất hiện tại hai (hoặc nhiều) vị trí trong xâu. Nhiệm vụ của bạn là tìm xâu con lặp lại dài nhất trong một xâu cho trước.

Dữ liệu vào

Dòng đầu tiên chứa một xâu có độ dài ~n~ gồm các ký tự a–z.

Kết quả

In ra xâu con lặp lại dài nhất. Nếu có nhiều khả năng, bạn có thể in ra bất kỳ xâu nào trong số đó. Nếu không có xâu con lặp lại, in ra ~-1~.

Giới hạn

• ~1 \le n \le 10^5~

Ví dụ

Dữ liệu vào:

cabababc

Kết quả:

abab