시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB76252550.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.

예제 입력 1

bab

예제 출력 1

2 1

예제 입력 2

dude

예제 출력 2

4 3
3 2

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > The UK & Ireland Programming Contest > UKIEPC 2017 D번

  • 문제를 만든 사람: Robin Lee