Tiền tố trùng Hậu tố

Cho xâu $s$ gồm các chữ cái Latin in hoa, độ dài $|s|$.

Một xâu con của $s$ là một đoạn liên tiếp các ký tự của $s$. Tiền tố độ dài $l$ là $s[1..l]$, hậu tố độ dài $l$ là $s[|s|-l+1..|s|]$.

Hãy tìm mọi độ dài $l$ sao cho tiền tố độ dài $l$ của $s$ trùng với hậu tố độ dài $l$ của $s$. Với mỗi $l$ như vậy, đếm xem tiền tố độ dài $l$ xuất hiện bao nhiêu lần dưới dạng xâu con của $s$ (các lần xuất hiện được phép chồng lấn nhau).

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$.

Dữ liệu ra

• Dòng đầu chứa số nguyên $k$ là số độ dài $l$ thỏa mãn tiền tố độ dài $l$ trùng hậu tố độ dài $l$.
• $k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $c_i$: tiền tố độ dài $l_i$ trùng với hậu tố độ dài $l_i$ và xuất hiện $c_i$ lần trong $s$ dưới dạng xâu con. In các cặp theo thứ tự $l_i$ tăng dần.

Ràng buộc

• $1\le |s|\le {10}^5$
• $s$ chỉ gồm các chữ cái Latin in hoa từ A đến Z.

Ví dụ