Arranging Participants by Performance

You are given a set of test cases. In each test case, there are several participants each identified by an ID along with their performance time. Your task is to sort the participants in ascending order of their performance times. If two participants have the same performance time, sort them by their IDs in ascending order.

Formally, you are given an integer t representing the number of test cases. For each test case, an integer n is provided which denotes the number of participants. Then follow n lines, each containing a string in the format ID:time where ID is a positive integer and time is a non-negative integer. Sort the participants such that if participant A and participant B have performance times \( t_A \) and \( t_B \) respectively, then A comes before B if

[ \begin{cases} t_A < t_B, \quad \text{or} \ t_A = t_B \text{ and } ID_A < ID_B. \end{cases} ]

Output the sorted list of participant IDs for each test case in a single line, with each ID separated by a single space.

inputFormat

The input is read from stdin and has the following format:

T
n1
ID1:time1
ID2:time2
...
IDn1:timen1
n2
... (and so on for T test cases)

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer n denoting the number of participants.
• Each of the next n lines contains a string in the format ID:time.

outputFormat

For each test case, output a single line on stdout containing the IDs of the participants sorted as described, separated by spaces.

## sample

2
3
101:5
102:3
103:5
4
201:10
202:5
203:10
204:2

102 101 103
204 202 201 203

</p>