Deranging Hat

A sorting network is a list of pairs of integers $(A_1, B_1), (A_2, B_2), \ldots$. Applying a pair $(A, B)$ to a string follows a single rule. If the $A$-th character is not smaller than the $B$-th character, swap the two characters, and otherwise leave the string as it is. The pairs of the list are applied one after another, from the first pair to the last.

An arranging hat lays out the letters it is given in ascending order. A deranging hat runs the other way. It starts from those sorted letters and puts the original word back together.

You are given a string $S$ of lowercase letters. Find a sorting network that turns the sorted letters of $S$ back into $S$.

The first line contains a string $S$ of lowercase Latin letters, 'a' to 'z'. ($1 \le |S| \le 1000$)

Several sorting networks usually work. Only the list built by the following rule is accepted.

Let $T$ be the string $S$ with its characters sorted in ascending order. Set the string $X$ to $S$ and start with an empty list. For $i = 1, 2, \ldots, |S|$ in this order, do the following. If $X_i = T_i$, do nothing. Otherwise take the smallest $j$ with $j > i$ and $X_j = T_i$, append the pair $(j, i)$ to the end of the list, then swap $X_i$ and $X_j$. Such a $j$ always exists.

Print the pairs of the list in the reverse of the order in which they were appended, one pair per line, the two integers separated by a single space. Print nothing if the list is empty. The list holds at most $|S| - 1$ pairs, so the output never exceeds 10000 lines, and every printed integer is between $1$ and $|S|$. Applying this list to $T$ gives $S$.