Índice de palabras X24468

Un índice de un texto es una lista de todas las palabras que aparecen en él, junto con las posiciones donde se encuentran. Por ejemplo, dado el texto:

the cat sat on the mat the cat

el índice sería:

cat: 2 8
mat: 6
on: 4
sat: 3
the: 1 5 7

Fijaos en que las palabras del índice están ordenadas alfabéticamente, y las posiciones de cada palabra también están ordenadas.

Haced un programa que lea una secuencia de palabras y muestre el índice.

Observación

En este problema el centro de interés es la eficiencia. Hay que encontrar una forma inteligente de almacenar las palabras y sus posiciones para evitar búsquedas innecesarias.

Entrada

La entrada es una secuencia de palabras (en minúsculas, sin espacios internos), una por línea, acabada por fin de entrada. La primera palabra tiene la posición 1.

Salida

Para cada palabra diferente que aparece en el texto, se escribe una línea con la palabra, seguida de : y un espacio, y a continuación las posiciones donde aparece, ordenadas de menor a mayor y separadas por espacios. Las palabras se escriben en orden alfabético.