Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TRAPEZ08 - Trapézio

A família Stropovich é conhecida mundialmente no mundo do circo por seus incríveis números de trapézio. É uma família numerosa, e todos os seus membros de várias gerações participam dos números de trapézio. Bem, quase todos os membros da família. Percival Stropovich, um garoto brilhante mas desajeitado, nunca pôde participar desses espetáculos, pois sua presença é certeza de desastre.

Mas finalmente o Sr. Postrovich Stropovich, patriarca da família, encontrou uma atividade para o desajeitado garoto, quando soube que Percival tinha ganho uma medalha na Olimpíada de Informática. Como Percival é um excelente programador, foi escalado para uma tarefa muito importante: verificar se é possível realizar o número dos sonhos de todos na família Stropovich. O número desejado é colocar todos os membros da família pendurados em um único trapézio, formando uma linha de trapezistas, de modo que o primeiro trapezista segure o segundo trapezista, o segundo trapezista segure o terceiro trapezista, e assim por diante, até o último trapezista da família.

Na família há trapezistas mais fortes e mais fracos, mais pesados e mais leves. Percival conhece o peso e a força (capacidade de aguentar o peso dos trapezistas abaixo dele) de cada trapezista de sua família. Sua tarefa é determinar uma ordem em que cada trapezista segura no máximo um peso menor ou igual à sua capacidade, de forma que todos os trapezistas da família fiquem pendurados em um mesmo trapézio.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha do conjunto de testes contém um número inteiro N que indica o número de trapezistas (1 ≤ N ≤ 105). Os trapezistas são identificados por números de 1 a N.

Cada uma das N linhas seguintes contém um par de inteiros P e F que representam respectivamente o peso do trapezista (1 ≤ P ≤ 104) e sua força (0 ≤ F ≤ 109).

Saída

Se é possível executar o número de acordo com as condições descritas acima, seu programa deve imprimir, na saída padrão, uma lista com N inteiros, um em cada linha, representando a ordem em que os trapezistas devem estar pendurados no trapézio. O primeiro número da lista deve corresponder ao trapezista que está no trapézio (não é seguro por ninguém), o último número da lista ao trapezista que não segura ninguém. Se houver mais de uma ordem possível de trapezistas, imprima a que tem menor ordem lexicográfica. Caso não seja possível executar o número, seu programa deve imprimir uma linha contendo a palavra ‘IMPOSSIVEL’ (sem acento).

(Nota: a ordem lexicográfica da lista a1, a2, . . . aN é menor do que a da lista b1, b2, . . . bN se para algum 1 ≤ i ≤ N temos ai < bi e o prefixo a1, a2, . . . ai−1 é igual ao prefixo b1, b2, . . . bi−1)

Exemplo

Entrada:
2
100 900
1000 100

Saída:
2
1

Entrada:
3
100 100
100 100
100 100

Saída:
IMPOSSIVEL

Entrada:
3
100 200
100 200
100 200

Saída:
1
2
3


Adicionado por:Wanderley Guimarăes
Data:2012-07-17
Tempo limite:0.300s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva IOI 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.