Một xâu con được gọi là lặp lại nếu như nó xuất hiện ở ít nhất hai vị trí khác nhau trong một xâu khác. Bạn được cho một xâu, và nhiệm vụ của bạn là phải tìm xâu con lặp lại có độ dài lớn nhất.

Input

• Dòng đầu tiên và duy nhất của input chứa một xâu có độ dài \(n\), gồm các kí tự in thường a - z.

Output

• In ra xâu con lặp lại có độ dài lớn nhất. Nếu có nhiều xâu con như vậy thì có thể in ra xâu bất kì. Còn nếu không có xâu con lặp lại nào thì hãy in ra -1.

Constraints

• \(1 \leq n \leq 10^5\)

Example