Cho xâu \(S\). In ra mảng hậu tố dưới dạng vị trí của các hậu tố, và cùng với LCP của mỗi cặp hậu tố kề nhau.

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 1000\)).

Định dạng đầu ra

• Dòng 1: Suffix Array.
• Dòng 2: LCP array.

Ví dụ

Input:

banana

Output:

5 3 1 0 4 2
0 0 3 0 2 0

Ràng buộc

• 100% số điểm: \(|S| \le 1000\).