Sort Items by Quantity and ID

You are given a list of n items. Each item is represented by an integer item ID and an integer quantity.

Your task is to sort the items according to the following criteria:

• First, by quantity in descending order (i.e., higher quantities come first).
• If two items have the same quantity, sort them by item ID in ascending order.

Formally, if an item is represented as \( (id, qty) \), then items should be sorted based on the key \( (-qty, id) \).

Print the sorted list of item IDs in one line separated by spaces.

inputFormat

The first line of input contains a single integer n representing the number of items.

The following n lines each contain two space-separated integers: the item ID and its quantity.

Example:

5
1001 10
1002 15
1003 10
1004 12
1005 15

outputFormat

Output a single line containing the sorted item IDs separated by a single space.

For the example above, the output should be:

1002 1005 1004 1001 1003

## sample

5
1001 10
1002 15
1003 10
1004 12
1005 15

1002 1005 1004 1001 1003