• محدودیت زمان: ۲.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

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.

ورودی

One line containing one string of lowercase Latin letters (‘a’-‘z’), $S$, containing at most $1000$ characters.

خروجی

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.

مثال

ورودی نمونه ۱

bab

خروجی نمونه ۱

2 1

ورودی نمونه ۲

dude

خروجی نمونه ۲

4 3
3 2