Hãy tưởng tượng bạn là một nhà thám hiểm dũng cảm, đang bước vào một ngôi mộ cổ đại ở sâu trong lòng một Kim tự tháp. Trên hành trình của mình, bạn phát hiện ra một cánh cửa khổng lồ, bao phủ bởi những biểu tượng bí ẩn và những ký tự lạ. Bạn nhận ra đây không phải là một cánh cửa bình thường – nó là một mật mã, chỉ có thể mở ra khi bạn giải mã đúng chuỗi ký tự cổ xưa được ghi trên cuộn giấy cổ đại.

Bản mật mã này, một chuỗi ký tự ~S~, chính là chìa khóa để mở cánh cửa dẫn đến kho báu vô giá. Nhưng điều này không đơn giản – bạn phải tìm ra chuỗi con liên tiếp dài nhất, có nhiều hơn một ký tự, xuất hiện nhiều lần nhất và xuất hiện ít nhất hai lần trong chuỗi ký tự ~S~.

Yêu cầu: Hãy giúp nhà thám hiểm tìm ra mật mã duy nhất để mở cánh cửa huyền bí.

Input

• Một dòng duy nhất chứa chuỗi ~S~ dài không quá ~10^5~ ký tự, gồm các ký tự chữ cái thường.

Output

• Dòng 1: Số lần xuất hiện nhiều nhất của chuỗi con tìm được.
• Dòng 2: Chuỗi con tìm được. Nếu có nhiều chuỗi con như vậy, hãy chọn chuỗi có giá trị từ điển nhỏ nhất.

Sample Input 1

cbabcbab

Sample Output 1

2
cbab

Sample Input 2

bbbaaaccc

Sample Output 2

2
aa

Subtasks