3326 - ICPC LEK-Team

Created by Yonny Mondelo Hernández
Added by ymondelo20 (2015-06-14)
Limits
Total Time: 20000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Lolek, Volek and Molek (the LEK-Team for programming contests) enjoy programming competitions, and of course they love to solve new problems. This time they are playing some game with strings. They have a sequence of N names: S_1, S_2, ..., S_N in an arbitrary order and not particular distribution. Names are conveniently numbered between 1 and N.

The game is simple. Each time one of them picks a position i between 1 and N, the other members of the team must find (if it exists) the closest position j to the right of i (i.e., j > i) such that:
1) S_j is lexicographically greater than the selected name S_i, and
2) there is no other name S_k located strictly between i and j (i.e., i < k < j) which is lexicographically less than S_j.

The LEK-Team needs to focus on skills and therefore you have been appointed to carry out this important task.
Lolek, Volek y Molek (LEK-Team para los concursos de programación) disfrutan de las competiciones de programación, y por supuesto les encanta resolver nuevos problemas. Esta vez están jugando un juego con cadenas. Ellos tienen una secuencia de N nombres: S_1, S_2, ..., S_N en un orden arbitrario y sin una distribución particular. Los nombres están convenientemente numerados entre 1 y N.

El juego es simple. Cada vez que uno de ellos escoge una posición i entre 1 y N, los demás miembros del equipo deben encontrar (si existe) la posición j más cercana a la derecha de i (es decir, j > i) tal que:
1) S_j es lexicográficamente mayor que el nombre seleccionado S_i, y
2) no hay otro nombre S_k ubicado estrictamente entre i y j (es decir, i < k < j) que es lexicográficamente menor que S_j.

LEK-Team tiene que centrarse en las habilidades y por lo tanto usted ha sido designado para llevar a cabo esta importante tarea.
Lolek, Volek and Molek (the LEK-Team for programming contests) enjoy programming competitions, and of course they love to solve new problems. This time they are playing some game with strings. They have a sequence of N names: S_1, S_2, ..., S_N in an arbitrary order and not particular distribution. Names are conveniently numbered between 1 and N.

The game is simple. Each time one of them picks a position i between 1 and N, the other members of the team must find (if it exists) the closest position j to the right of i (i.e., j > i) such that:
1) S_j is lexicographically greater than the selected name S_i, and
2) there is no other name S_k located strictly between i and j (i.e., i < k < j) which is lexicographically less than S_j.

The LEK-Team needs to focus on skills and therefore you have been appointed to carry out this important task.

Input specification

The first line of input contain an integer T (1 <= T <= 100) denoting the number of test cases. T lines follows each one containing an integer N (1 <= N <= 10^3) representing the number of names in the list, followed by N space-separated names; the elements of the list respectively. Names are non-empty and you can safely assume that all given names are composed by at most 8 lowercase letters without blank spaces.
La primera línea de la entrada contiene un número entero T (1 <= T <= 100) que indica el número de casos de prueba. Siguen T líneas y cada una de ellas contiene un número entero N (1 <= N <= 10 ^ 3) que representa la cantidad de nombres en la lista, seguido de N nombres separados por un espacio en blanco; los elementos de la lista respectivamente. Los nombres contienen al menos una letra y puede asumir con seguridad que todos los nombres están compuestos por un máximo de 8 letras minúsculas sin espacios en blanco.
The first line of input contain an integer T (1 <= T <= 100) denoting the number of test cases. T lines follows each one containing an integer N (1 <= N <= 10^3) representing the number of names in the list, followed by N space-separated names; the elements of the list respectively. Names are non-empty and you can safely assume that all given names are composed by at most 8 lowercase letters without blank spaces.

Output specification

For each case output a line with N space-separated integer numbers not greater than N representing the respective S_j (if it exists) for each name in the list. You must print first the solution for S_1, then the solution for S_2, and so on until solution for S_N. If there is no solution for some name in the list you must print -1 instead (note that the last number must be always -1).
Por cada caso usted debe imprimir una línea con N números enteros no mayores que N separados por un espacio en blanco, que representan el respectivo S_j (si existe) para cada nombre en la lista. Debe imprimir primero la solución para S_1, luego la solución para S_2, y así sucesivamente hasta que la solución para S_N. Si no existe una solución para algún nombre en la lista debe imprimir -1 en su lugar (tenga en cuenta que el último número debe ser siempre -1).
The first line of input contain an integer T (1 <= T <= 100) denoting the number of test cases. T lines follows each one containing an integer N (1 <= N <= 10^3) representing the number of names in the list, followed by N space-separated names; the elements of the list respectively. Names are non-empty and you can safely assume that all given names are composed by at most 8 lowercase letters without blank spaces.

Sample input

3
1 myname
5 acmicpc lekteam lolek molek volek
9 zzz lolek molek volek acm icpc acm acmicpc nextname

Sample output

-1
2 3 4 5 -1
-1 3 4 -1 6 -1 8 9 -1

Hint(s)