Classificados de Sementes

A famosa empresa agrônoma, EDA (Estudos e Desenvolvimento Agrônomos), está realizando a coleta de resultados da qualidade das sementes de todos os produtos que podem ser plantados no planeta terra. Um dos objetivos desta seleção está em descobrir se temos alguma semente que poderá ser plantada em um outro planeta, como marte. O problema que esta renomada empresa está enfrentando é como descobrir quais são as melhores sementes.

Laboratórios do mundo todo mandaram informações de muitas sementes, na casa dos bilhões, e a EDA precisa urgentemente da lista (ordenada) das $k$ melhores sementes para realizar o experimento. O grupo técnico da EDA já tentou ordenar esse conjunto de dados e não obteve sucesso, nem mesmo o quicksort com a melhor estratégia consegue ordenar este vetor. E para conseguir resolver este problema, a EDA chamou você para auxiliar nesta difícil tarefa.

Entrada

A entrada possui um único caso de teste. A primeira linha do caso de teste possui um número $k$ ($1 \leq k \leq 10^9$) representando quantas sementes você deverá selecionar (baseada no melhor Valor), a seguir existe um número indeterminado de linhas (sabemos que não passa de $10^7$ entradas e você pode assumir que cabe na memória, pois a EDA disponibilizou uma máquina grande). Cada linha da entrada possui $2$ números inteiros $S$ ($0 \leq S \leq 2^{50}$) e $N$ ( $-10^9 \leq N \leq 10^9$), representando o código da Semente e a Nota da qualidade, respectivamente.

Saída

A saída deverá ser composta por um conjunto de linhas que representam as $k$ melhores sementes. Quanto menor o valor de $N$ melhor é a semente.

A saída deve estar ordenada pelo código da semente (da menor para a maior).

Havendo empate nas notas da semente o desempate será feito pelo menor código de semente.

Exemplos

Exemplo de Entrada

4
30553 3265
27183 26616
2414 -30329
16682 23006
20027 5010
10315 32560
23488 17242
26565 -22549
2660 23760
10568 27930

Saída para o exemplo acima

2414 -30329
20027 5010
26565 -22549
30553 3265

Exemplo Entrada

3
10 232
32 656
4535 -222
56 -222
767 -222
943 -222
323 -222

Saída para o exemplo acima

56 -222
323 -222
767 -222

DICAS:

• Evite ordenar a entrada toda
• Cuidado com as sementes de nota iguais