D. Sort IT out

Dilbert complained that there was a huge mess on the company storage server, so management came up with a brilliant idea to make some order in the chaos: the lines of each text file on the server should be sorted.

Knowing that garbled text files aren't very useful (and management never withdraws a bad decision) the software engineer team worked out the following solution: for each sorted text file keep a list of the lines which should be swapped to get back the original content. This list itself should be sorted as well of course.

Dilbert asks for your help to find the minimum amount of line swaps for a given document. He notes that some documents contain repeated lines, which can make things a bit harder.

Note: you can request trace for this problem for -5 points. The trace output would contain a short hint about how the solution failed.

Input

The input is plain text (ASCII encoded and apart from the line endings only characters with byte code >=32 and <=126 can appear in the file)

Output

The output should be a sorted list of line number pairs (each line of the output should contain two decimal numbers separated by space and the lines should be sorted).

After sorting the lines of the given input text, it should be possible to restore the original content by swapping all the line pairs listed in the output in the order they appear.

Lines are numbered from 1. Sorting means lexicographical ascending order based on character codes. For example 'BOB' is less than 'alice' and '23 5' is less than '4 1'. The output should adhere to the input format.

The number of lines in the output should be minimal.

Example input

foo
bar
baz
egg
spam
quux

Example output

1 4
2 4
3 4
5 6