Toy Arrangement Challenge

You are given a series of test cases. In each test case you are given a list of toys. Each toy is described by a toy name (which may include spaces), a toy type and a popularity score. Your task is to sort the list of toys according to the following criteria:

• Sort by toy type in lexicographical ascending order.
• Within the same toy type, sort by popularity in descending order.
• If two toys have the same type and popularity, sort by toy name in lexicographical ascending order.

After sorting, print the list of toys. Each toy should be printed in a separate line in the format: toy_name toy_type popularity.

inputFormat

The input is read from standard input (stdin) and includes multiple test cases.

The first line of input contains a single integer T indicating the number of test cases. For each test case:

• The first line contains an integer N representing the number of toys.
• The next N lines each contain information about a toy. Each line consists of a toy name (which might contain spaces), followed by its toy type and its popularity score. The toy name is formed by all tokens except the last two, the penultimate token is the toy type, and the last token is the popularity (an integer).

All input is provided via stdin.

outputFormat

For each test case, output the sorted list of toys to standard output (stdout). Each toy should be printed on a new line in the format:

toy_name toy_type popularity

The toys from different test cases are printed in the order of input without any blank lines between test cases.

## sample

1
5
robot action 120
car action 200
doll fashion 150
truck action 120
bear fashion 150

car action 200
robot action 120
truck action 120
bear fashion 150
doll fashion 150

</p>