El Granjero Juan (GJ) mantiene una lista ordenada alfabéticamente de sus ~N~ vacas (~1 \leq N \leq 50 000~) pegada a la puerta del establo. Cada nombre de vaca está representado por una cadena distinta de entre ~1~ y ~20~ caracteres en minúsculas.

Siempre la alborotadora, Bessie la vaca altera la lista reordenando las vacas de la lista. Además, también cambia el orden de las letras en el nombre de cada vaca. Dada esta lista modificada, ayude al Granjero Juan a calcular, para cada entrada en la lista, las posiciones más bajas y más altas en la que posiblemente podría haber aparecido en la lista original.

Entrada

• Línea 1: Un solo número entero ~N~.

• Líneas 2…1+N: Cada una de estas líneas contiene el nombre reordenado de alguna vaca.

Ejemplo de Entrada

4
essieb
a
xzy
elsie

Detalles de la Entrada

Hay ~4~ vacas, con los nombres reordenados dados arriba.

Salida

• Líneas 1…N: La línea ~i~ debe especificar, para la cadena de entrada ~i~, la posición más baja y la posición más alta en la posible lista original del Granjero Juan, en que dicha cadena reordenada posiblemente podría haber aparecido.

Ejemplo de Salida

2 3
1 1
4 4
2 3

Detalles de la Salida

La cadena "a" habría aparecido primero en la lista de GJ sin importar cómo las letras de las cadenas se ordenaron originalmente. De manera similar, la cadena "xzy" habría aparecido al final, sin importar cómo, sus letras fueron reordenadas en la lista ordenada original. Las dos cadenas "essieb" y "elsie" ambas podrían haber ocupado las posiciones ~2~ o ~3~, dependiendo del ordenamiento de sus letras originales (por ejemplo, "bessie" (posición ~2~) y "elsie" (posición ~3~), frente a "sisbee" (posición ~3~) e "ilees" (posición ~2~)).