뒤섞는 모자

정렬망은 정수 쌍의 목록 $(A_1, B_1), (A_2, B_2), \ldots$ 이다. 문자열에 쌍 $(A, B)$를 적용하는 규칙은 하나뿐이다. $A$번째 문자가 $B$번째 문자보다 작지 않으면 두 문자를 맞바꾸고, 작으면 문자열을 그대로 둔다. 목록에 적힌 쌍은 첫 번째부터 마지막까지 차례대로 적용한다.

정렬하는 모자는 받은 글자를 오름차순으로 늘어놓는다. 뒤섞는 모자는 정확히 반대로 움직인다. 오름차순으로 정렬된 글자에서 출발해 원래 단어를 되돌려 놓는다.

알파벳 소문자로 이루어진 문자열 $S$가 주어진다. $S$의 글자를 오름차순으로 정렬한 문자열에 적용하면 $S$가 되는 정렬망을 구한다.

첫째 줄에 알파벳 소문자로만 이루어진 문자열 $S$가 주어진다. ($1 \le |S| \le 1000$)

조건을 만족하는 정렬망은 보통 여러 개다. 그중 다음 규칙으로 만든 목록 하나만 정답으로 인정한다.

$S$의 글자를 오름차순으로 정렬한 문자열을 $T$라고 하자. 문자열 $X$를 $S$로 두고 빈 목록에서 시작한다. $i = 1, 2, \ldots, |S|$ 순서로 다음을 반복한다. $X_i = T_i$이면 아무것도 하지 않는다. 그렇지 않으면 $j > i$이면서 $X_j = T_i$인 가장 작은 $j$를 골라 쌍 $(j, i)$를 목록 끝에 덧붙이고 $X_i$와 $X_j$를 맞바꾼다. 이런 $j$는 항상 존재한다.

목록에 덧붙인 순서의 역순으로 쌍을 출력한다. 한 줄에 한 쌍씩, 두 정수를 공백 하나로 구분한다. 목록이 비어 있으면 아무것도 출력하지 않는다. 목록의 길이는 $|S| - 1$ 이하이므로 출력은 10000줄을 넘지 않고, 출력하는 정수는 모두 $1$ 이상 $|S|$ 이하다. 이 목록을 $T$에 적용하면 $S$가 된다.