Find The Next Letter


Anders the cat is playing with their party´s partners Vinagrito and Klaus, playing with letters this time; he has a list of N lowercase letters in an arbitrary order and not particular distribution. Letters are conveniently numbered between 1 and N. The game is simple; each time one of them select some letter (their respective position) of the list, other cats must find (if exist) the first letter (their respective position) to the right in the given list which is greater to the selected letter.

Ander hates not to win, so he needs your help for finding the solution rapidly.


In the first line an integer number T ≤ 1000 will be given corresponding to the number of test cases. The next T lines contains an integer number 1 ≤ N ≤ 105 representing the amount of letters in the list, followed by N lowercase letters as a whole string of size N which are the elements of the list itself. You can safely assume that the sum of the sizes of all the string will not exceed 105. The first line contains T, the number of test cases.


For each case output a line with N space-separated integer numbers not greater than N representing the respective position of the solution for each letter in the list. You must print first the solution for the first letter, then the solution for the second letter, and so on. If there is no solution for some letter/position in the list you must print -1 instead (note that the last number must be always -1).

Example input
1 r
5 abcde
9 uprdesoft
Example output
2 3 4 5 -1
-1 3 6 5 6 9 9 9 -1
Time and memory limit:

  • 2 seconds
  • 256MB

Problem source: COJ