Stable Descending Tuple Sort

You are given n tuples. Each tuple contains two integers. Your task is to sort the tuples in descending order based on their second element. If two tuples have the same second element, you must preserve their original order (i.e., perform a stable sort).

In other words, for a tuple \((a, b)\), the sorting key is \(b\). This can be mathematically represented as sorting by the function \(f(a,b)=b\) in descending order.

inputFormat

The first line of input contains an integer n denoting the number of tuples.

Each of the following n lines contains two space-separated integers, representing a tuple.

outputFormat

Output n lines, each containing two space-separated integers. The tuples should appear in sorted order based on the second element in descending order while preserving the relative order for tuples with the same second value.

4
1 3
2 2
3 1
4 2

1 3
2 2
4 2
3 1