Hàm Xâu

Cho xâu có $n$ ký tự (đánh số từ $1$). Tính hai hàm xâu:

• $z(i)$: độ dài xâu con dài nhất bắt đầu tại vị trí $i$ đồng thời là tiền tố của xâu. Quy ước $z(1)=0$.
• $\pi (i)$: độ dài xâu con dài nhất kết thúc tại vị trí $i$, đồng thời là tiền tố của xâu, và có độ dài tối đa $i-1$.

Dữ liệu vào

Một dòng duy nhất chứa xâu có độ dài $n$.

Dữ liệu ra

Dòng đầu tiên in ra $n$ giá trị $z(1),z(2),\dots ,z(n)$.

Dòng thứ hai in ra $n$ giá trị $\pi (1),\pi (2),\dots ,\pi (n)$.

Ràng buộc

• $1\le n\le {10}^6$
• Xâu chỉ chứa ký tự a-z

Ví dụ