Sort Dictionary by Values in Descending Order

You are given a collection of key-value pairs, where each key is a string and each value is an integer. Your task is to sort these pairs in descending order according to their values. In the event of a tie (i.e. when two or more keys have the same value), the order should be the same as the original input (i.e. a stable sort).

More formally, if you are given a sequence of pairs ( (k_i, v_i) ) for ( i=1,2,\dots,n ), you should arrange them such that [ v_{\sigma(1)} \geq v_{\sigma(2)} \geq \cdots \geq v_{\sigma(n)} ] with the additional condition that if ( v_{\sigma(i)} = v_{\sigma(i+1)} ), then ( \sigma(i) < \sigma(i+1) ) (i.e. the relative order of keys with equal values remains unchanged).

The input is read from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line contains an integer ( n ) representing the number of key-value pairs. Each of the following ( n ) lines contains a string and an integer separated by a space. The string represents the key and the integer represents the value.

outputFormat

Output ( n ) lines, each line containing a key and its corresponding value separated by a space, in the order defined above.## sample

3
apple 2
banana 4
cherry 3

banana 4
cherry 3
apple 2