Scrambled Letters

Farmer John keeps an alphabetically-ordered list of his $N$ cows ($1 \le N \le 50{,}000$) taped to the barn door. Each cow's name is a distinct string of between 1 and 20 lowercase letters.

Always the troublemaker, Bessie the cow alters the list by re-ordering the cows. On top of that, she scrambles the letters within each cow's name. Given this modified list, help Farmer John determine, for each entry, the lowest and highest positions at which the original form of that entry (some rearrangement of the same letters) could have appeared in the original alphabetically-ordered list.

• Line 1: A single integer $N$.
• Lines 2 to $N+1$: Each of these lines contains the re-ordered name of one cow.

• Lines 1 to $N$: Line $i$ should give, for input string $i$, the lowest and highest positions in Farmer John's original list at which the original form of string $i$ could have appeared, separated by a single space.

In the example, there are 4 cows whose re-ordered names are essieb, a, xzy, and elsie.

The string "a" would have appeared first on the list no matter how its letters were arranged, and likewise the string "xzy" would have appeared last no matter the ordering of its letters. The two strings "essieb" and "elsie" could each have occupied either position 2 or position 3, depending on their original letter orderings. For example, "bessie" (position 2) and "elsie" (position 3), versus "sisbee" (position 3) and "ilees" (position 2).