15030번 - Deranging Hat 스페셜 저지다국어

문제

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 ≤ A_i, B_i ≤ |S|) giving the i-th operation to perform.

제한

힌트