In the wizarding world of security, there are two kinds of researcher: the idealist arranging hat and the mercenary deranging hat.</p>

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.

예제 입력 1

bab

예제 출력 1

2 1

예제 입력 2

dude

예제 출력 2

4 3
3 2