Gần đây An bắt đầu đăng ký một công ty cung cấp các phần mềm trí tuệ nhân tạo và đã nộp các hồ sơ cần thiết. Các người bạn thân đã nói với An rằng trong danh sách xét duyệt hồ sơ, các công ty được liệt kê theo thứ tự từ điển tăng dần của tên công ty. An không biết tên các công ty khác trong danh sách, nhưng anh ta quyết định xem xét các khuyến nghị và đổi tên công ty của mình để nó có thứ tự từ điển trong danh sách càng nhỏ càng tốt.

Vì An đã nộp hồ sơ nên anh ta không thể thay đổi hoàn toàn tên của công ty, nhưng anh ta có thể lấy lý do mắc lỗi soạn thảo là hoán đổi hai chữ cái bất kỳ trong tên. Bạn hãy giúp An chọn tên công ty mới bằng cách hoán đổi hai chữ cái bất kỳ trong tên hoặc giữ nguyên tên hiện tại, để cho tên công ty có thứ tự từ điển trong danh sách càng nhỏ càng tốt.

INPUT

Gồm một dòng chứa một xâu gồm các chữ cái tiếng Anh viết thường (từ a đến z) có độ dài ~n~ (~2 ≤ n ≤ 10^6~) là tên công ty của An.

OUTPUT

Một xâu là tên công ty mới. Nếu tên không thay đổi thì in tên gốc.

SAMPLE INPUT 1

aefbz

SAMPLE OUTPUT 1

abfez

Trong ví dụ đầu tiên, An có thể giữ nguyên tên công ty aefbz, hoặc hoán đổi các cặp ký tự ở các vị trí ~(1, 2)~, ~(1, 3)~, ~(1, 4)~, ~(1, 5)~, ~(2, 3)~, ~(2, 4)~, ~(2, 5)~, ~(3, 4)~, ~(3, 5)~, ~(4, 5)~ để được các tên công ty mới tương ứng là aefbz, afebz, ebafz, zefba, afebz, abfez, azfbe, aefbz, aezbf, aefzb. Trong các tên trên, việc hoán đổi cặp ký tự ở vị trí ~(2, 4)~ cho tên abfez có thứ tự từ điển nhỏ nhất.

SAMPLE INPUT 2

abc

SAMPLE OUTPUT 2

abc

Trong ví dụ thứ hai, An giữ nguyên tên công ty vì sẽ cho tên có thứ tự từ điển nhỏ nhất.

SUBTASKS

• Có ~20 \%~ số test thỏa mãn ~n \le 10~.
• Có ~20 \%~ số test thỏa mãn ~n \le 100~.
• Có ~20 \%~ số test thỏa mãn ~n \le 3000~.
• Có ~20 \%~ số test thỏa mãn ~n \le 5 \times 10^4~.
• Có ~20 \%~ số test không có ràng buộc gì thêm.