---------- In the wizarding world of security, there are two kinds of researcher: the idealist arranging hat and the mercenary deranging hat. As we learned last year, an arranging hat carefully sorts out any list of letters given to it into ascending order. However, a deranging hat performs the exact opposite function: putting a sorted string of letters back into its original order. The tool of choice for today’s discerning headwear is a sorting network: a sequence of instructions represented by a list of pairs of numbers $A_i$ and $B_i$, meaning that if at step $i$ the $A$-th item in the string is not already smaller than the $B$-th item, they should be swapped immediately. Given a specific word $W$, output a sorting network that the deranging hat can use to form the word from its original sorted letters. # Input One line containing one string of lowercase Latin letters (`‘a’-‘z’`), $S$, containing at most $1000$ characters. # Output Output at most 10000 lines, each containing two integers $A_i$ and $B_i$ ($1 \le A_i, B_i \le |S|$ ) giving the $i$-th operation to perform. ## Sample Input 1 ``` bab ``` ## Sample Output 1 ``` 2 1 ``` ## Sample Input 2 ``` dude ``` ## Sample Output 2 ``` 4 3 3 2 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> اگر دنباله‌ی خروجی را از آخر به اول نگاه کنیم معادل این است که در ابتدا آرایه فعلی را داریم و در هر مرحله اگر $A_i$ کوچکتر از $B_i$ بود، جای آن دو را با هم عوض کن. حال با این مدل نگاه کردن می‌توانیم بر روی رشته‌ی فعلی مراحل را پیاده کنیم. هر دفعه کوچک‌ترین حرفی (از نظر الفبایی) که سر جایش نیست را در نظر گرفته و آن را با یک جا به جایی به سر جایش بیاوریم. این‌گونه مرحله به مرحله در حال ساختن رشته‌ی صعودی از چپ به راست هستیم. در نهایت نیز جفت‌های همه‌ی مراحلمان را به ترتیب برعکس اجرا شدن خروجی می‌دهیم و طبق بند فوق، این همان دنباله‌ي خواسته شده‌ی مسئله است. اگر اندازه‌ی رشته‌ی ورودی را $l$ در نظر بگیریم، حداکثر $l$ مرحله کار بالا را انجام می‌دهیم و تایم برنامه نیز از $O({l^2})$ می‌باشد چرا که برای پیدا کردن جفت مورد نظر در هر مرحله حداکثر $l$ کاراکتر را چک می‌کنیم. </details>