Tí và Tèo là đôi bạn thân. Tí đi chơi, Tèo đi học. Đường ngang dọc đều dẫn tới nơi...
Một hôm, cô giáo giao bài tập nhóm cho Tí và Tèo. Nhưng do Tèo ham chơi mà bỏ quên bài tập nhóm, chỉ còn lại Tí phải căng não làm bài tập.
Đề bài cho một xâu ~s~ chỉ gồm các chữ cái tiếng anh viết thường. Bạn phải chọn một xâu con liên tiếp trong ~s~(xâu con được chọn phải khác xâu rỗng) và lùi các kí tự trong xâu được chọn theo qui tắc a
~\to~ z
, b
~\to~ a
,c
~\to~ b
,..., z
~\to~ y
. Nhiệm vụ của bạn là tìm ra xâu có thứ tự từ điển nhỏ nhất có thể thu được từ xâu ~s~.
Bạn hãy viết chương trình giúp Tí giải quyết vấn đề này nhé.
Dữ liệu vào
Một dòng duy nhất chứa xâu ~s~~(1 \le |s| \le 1000000)~.
Kết quả ra
Một dòng duy nhất chứa xâu con có thứ tự từ điển nhỏ nhất có thể thu được từ xâu ~s~.
Chú ý: xâu ~a_{1}a_{2}a_{3}...a_{n}~ có thứ tự từ điển nhỏ hơn xâu ~b_{1}b_{2}b_{3}...b_{n}~ khi và chỉ khi tồn tại chỉ số ~i~ sao cho:
- ~a_{i} < b_{i}~~(1 \le i \le n)~.
- Đồng thời, với mọi ~1 \le j < i~, ta luôn có ~a_{j} = b_{j}~.
Ràng buộc
- Có ~30\%~ số test ứng với ~(1 \le |s| \le 500)~.
- Có ~30\%~ số test ứng với ~(500 \le |s| \le 5000)~.
- Còn lại ~40\%~ số test không có ràng buộc gì thêm.
Ví dụ
Dữ liệu vào
tinhoc
Kết quả ra
shmgnb
Giải thích
Ở ví dụ, tinhoc
là xâu con liên tiếp được chọn.
Bình luận