# رشته ی دوست داشتنی time limit per test: 1 seconds memory limit per test: 64 megabytes ---------- مردم شهر استرینگ آباد علاقه ی زیادی به بازی با رشته های مختلف دارند. آن ها برای رشته هایی از مدل های خاص اسم های خاص میگذارند. برای مثال به رشته هایی که با حرف a شروع میشوند ، رشته های کوچولو میگویند. از جمله رشته های معروفی که به چشم میخورد و بسیار مورد علاقه ی مردم است ، رشته ی دوست داشتنی نام دارد. به رشته ای دوست داشتنی گفته میشود که از دو طرف یکسان خوانده شود مانند aba یا cnnc. حال آن ها میخواهند با یک سری عملیات رشته های مختلف را با کمترین هزینه به یک رشته ی دوست داشتنی تبدیل کنند. 2 عمل مجاز وجود دارد برای تغییر رشته ها: ۱. جابجایی دو حرف از رشته که هزینه ای در بر نخواهد داشت. ۲. تغییر دادن یک حرف از رشته به حرف دیگر که هزینه ای برابر 1 واحد پول کالین خواهد داشت. حال از شما خواسته شده رشته ای دوست داشتنی ارائه دهید که با کمترین هزینه از رشته ی ورودی به دست می آید. ## ورودی در تنها خط ورودی یک رشته از حروف کوچک انگلیسی با طول کم تر از $10^5$ داده شده است ## خروجی در تنها خط خروجی رشته ی دوست داشتنی ای که با کمترین هزینه از رشته ی ورودی به دست می آید را نمایش دهید. اگر چند رشته ی دوست داشتنی با هزینه ی یکسان قابل دسترسی بود، رشته ای را معرفی کنید که از نظر الفبایی کوچک تر است. ## مثال ورودی abc خروجی aba