Thứ Tự Các Hậu Tố

Với xâu $S$ có độ dài $n$, hậu tố bắt đầu tại vị trí $i$ là xâu $S_i,\dots ,S_{n-1}$, trong đó các vị trí được đánh số từ $0$. Hãy sắp xếp toàn bộ $n$ hậu tố theo thứ tự từ điển và in ra vị trí bắt đầu của chúng theo thứ tự đó.

Input

• Dòng duy nhất chứa xâu $S$.

Output

• In $n$ số nguyên trên một dòng. Số thứ $j$ là vị trí bắt đầu của hậu tố đứng thứ $j$ trong thứ tự từ điển.

Constraints

• $1\le n\le 5\cdot 10^5$.
• $S$ chỉ gồm các chữ cái thường tiếng Anh từ $a$ đến $z$.
• Vị trí trong xâu được đánh số từ $0$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 3000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

cacao

1 3 0 2 4