Xét một xâu có độ dài \(n\), bắt đầu đếm từ 1. Nhiệm vụ của bạn là tính tất cả giá trị của hai hàm sau:

• \(z(i)\) là độ dài lớn nhất của xâu con bắt đầu tại vị trí \(i\), và đồng thời xâu con này cũng là tiền tố của xâu ban đầu. Ta định nghĩa \(z(1)=0\).
• \(\pi(i)\) là độ dài lớn nhất của xâu con kết thúc ở vị trí \(i\), đồng thời cũng là tiền tố của xâu ban đầu, và có độ dài không vượt quá \(i-1\).

Hàm \(z\) được dùng trong thuật toán Z-algorithm, còn hàm \(\pi\) được dùng trong thuật toán KMP.

Input

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

Output

In ra hai dòng, mỗi dòng gồm \(n\) giá trị:

• Dòng thứ nhất chứa \(n\) số nguyên ứng với các giá trị của hàm \(z\).
• Dòng thứ hai chứa \(n\) số nguyên ứng với các giá trị của hàm \(\pi\).

Constraints

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

Example