Dãy con lớn nhất theo thứ tự từ điển

Cho một xâu $s$ khác rỗng chỉ gồm các chữ cái Latin in thường. Hãy tìm dãy con lớn nhất theo thứ tự từ điển của $s$.

Một dãy con của $s=s_1{s}_2\dots s_{|s|}$ là một xâu khác rỗng có dạng $s_{p_1}{s}_{p_2}\dots s_{p_k}$ với $1\le p_1<p_2<\dots <p_k\le |s|$, tức là xâu thu được bằng cách xoá đi một số (có thể bằng $0$) ký tự của $s$ và giữ nguyên thứ tự các ký tự còn lại.

Xâu $x$ lớn hơn xâu $y$ theo thứ tự từ điển nếu tồn tại vị trí $r$ sao cho $x_1=y_1,\dots ,x_r=y_r$ và $x_{r+1}>y_{r+1}$, hoặc nếu $y$ là tiền tố thực sự của $x$. Các ký tự được so sánh theo mã ASCII.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ gồm các chữ cái Latin in thường.

Dữ liệu ra

In ra dãy con lớn nhất theo thứ tự từ điển của $s$.

Ràng buộc

• $1\le |s|\le {10}^5$
• $s$ chỉ gồm các chữ cái từ a đến z

Ví dụ