ランキングアルゴリズムを高速化しよう

昔の大会では、ソフトウェアエンジニアたちがバブルソートを用いたランキングアルゴリズムを実装していました。当時は参加者数がそれほど多くなかったので、それでも十分に機能していたのです。しかし、現在では参加者数がとても多くなり、アルゴリズムを高速化することが求められています。

各チームには固有の番号（識別子）とスコアがあり、スコアが高い順（高いスコアを先に、低いスコアを後に）になるように並べ替えなければなりません。また、同じスコアのチームについては、入力で登場した順番が保たれるようにしなければなりません。つまり、安定ソートを実装する必要があります。

入力

最初の行には、単一の整数 n (1 ≤ n ≤ ) が与えられます。

続く n 行には、チームの固有の識別子とスコアを表す、スペース区切りのペア () が与えられます。

出力

プログラムは n 行を出力します。各行にはチームの id とスコアのペアを出力してください。

例