Masala H

Alisher yangi kod yozishni yaxshi ko‘radi. Bir kuni u kichik lotin harflaridan iborat bo‘ilgan, uzunligi \(n\) ga teng bir satr — s bilan o‘ynay boshladi.

U o‘z oldiga quyidagi qiziqarli vazifani qo‘ydi: faqat bitta marta istalgan ikkita belgining o‘rnini almashtirib, satrni leksikografik jihatdan eng kichik holatga keltirish.

Alisherga bu muammoni hal qilishda yordam bering! Eng kichik bo‘lishi mumkin bo‘lgan natija satrini chiqaruvchi dastur tuzing.

Bitta satr s.

Cheklovlar

• \(1 \leq |s| \leq 2 \times 10^5\)

Ko‘pi bilan bitta swapdan keyingi eng kichik satr.