Danh sách

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 bạn của An đã 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

• Vào 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 \le n \le 10^6)\) là tên công ty của An.

Output

• Ghi ra 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.

Input

%
aefbz

Output

%
abfez

Input

%
abc

Output

%
abc

Notes

Trong ví dụ đầu tiên, An có thể giữ nguyên tên công ty là 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à eafbz, faebz, befaz, zefba, afebz, abfez, azfbe, aebfz, aefzb, aefbz. 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.

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

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm thỏa mãn: \(n \le 10\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thỏa mãn: \(n \le 100\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thỏa mãn: \(n \le 3000\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thỏa mãn: \(n \le 5 \times 10^4\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm: Không có thêm ràng buộc nào.