시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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 Ai and Bi, 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 Ai and Bi (1 ≤ Ai, Bi ≤ |S|) giving the i-th operation to perform.

예제 입력

bab

예제 출력

2 1

예제 입력 2

dude

예제 출력 2

4 3
3 2

힌트