Viền và tần suất xuất hiện

Bối cảnh và bài toán

Một hệ thống đồng bộ gói tin sử dụng các đoạn đầu đồng thời xuất hiện ở cuối chuỗi làm "mốc khóa". Với mỗi mốc như vậy, nhóm vận hành còn muốn biết đoạn khóa đó xuất hiện bao nhiêu lần trong toàn bộ thông điệp để đánh giá mức độ lặp cấu trúc.

Yêu cầu

Với mọi độ dài l sao cho tiền tố dài l cũng là hậu tố của s (cho phép l = |s|), hãy in l và số lần tiền tố đó xuất hiện trong s như một substring.

Input

Một dòng chứa chuỗi s.

Output

Dòng đầu in số lượng độ dài hợp lệ k. Sau đó in k dòng l c theo l tăng dần, với c là số lần xuất hiện.

Ràng buộc

• 1 <= |s| <= 2 * 10^5
• s gồm các chữ cái A..Z.

Chấm điểm

Ví dụ 1

Input

ABACABA

Output

3
1 4
3 2
7 1

Giải thích. Các border có độ dài 1, 3 và toàn chuỗi 7; số lần xuất hiện tương ứng là 4, 2 và 1.

Ví dụ 2

Input

AAA

Output

3
1 3
2 2
3 1

Giải thích. Chuỗi lặp mạnh nên mỗi prefix cũng là suffix và xuất hiện nhiều lần chồng lấn.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from: Codeforces Round 246 (Div. 2) – 432D – Prefixes and Suffixes.