Stable Priority Sorting of Cart Items

You are given a list of items from a shopping cart, where each item has a name and an associated priority. Your task is to sort these items in descending order of their priority. If two items have the same priority, they must retain their original order (i.e., the sort must be stable).

In mathematical terms, given items with priorities (p_i) for (i=1,2,\ldots,n), if (p_i = p_j) and (i < j) in the input, then (i) should appear before (j) in the output.

Implement a program that reads the list of items from standard input and writes the sorted list to standard output.

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), representing the number of items. Each of the following (n) lines contains a string (the item name) and an integer (the priority), separated by a space.

outputFormat

Output (n) lines, each containing the item name and its priority separated by a space, sorted in descending order by priority. Items with equal priorities must appear in the same order as in the input.## sample

5
apple 2
banana 1
carrot 5
date 3
eggplant 1

carrot 5
date 3
apple 2
banana 1
eggplant 1