SPOJ Brasil

João é dono de um website que auxilia pessoas a organizarem viagens, e precisa de sua ajuda para desenvolver um novo módulo que torne mais simples escolher hotéis.

Cidades turísticas normalmente possuem um número grande de hotéis. Algumas chegam a ter literalmente milhares deles. É praticamente impossível para uma pessoa comparar todos eles. Ao escolher hotéis, usamos alguns critérios. Por exemplo, numa cidade litorânea, podemos estar interessados em distância até à praia, preço, e qualidade (número de estrelas). Considere três hotéis hipotéticos:

• Hotel A: a 200 metros da praia, R$ 160,00 a diária, 4 estrelas;
• Hotel B: a 400 metros da praia, R$ 160,00 a diária, 3 estrelas;
• Hotel C: a 100 metros da praia, R$ 560,00 a diária, 5 estrelas.

Nesse exemplo, o Hotel B é igual-ou-pior ao Hotel A em todos os aspectos: é mais longe da praia, tem o mesmo preço, e menor qualidade. Então, nesse caso, certamente o Hotel A é uma escolha melhor que o Hotel B; o B nem precisa ser mostrado ao usuário. Já o Hotel C é melhor que o A em dois aspectos (mais próximo à praia, melhor qualidade) e pior em um (preço). Assim, não é possível afirmar a priori que ele é melhor ou pior que o Hotel A. O usuário precisa decidir entre os dois, dependendo do que acha mais importante.

Ou seja: um hotel X pode ser removido da lista que é mostrada ao usuário desde que exista um outro hotel Y tal que Y é melhor que X em pelo menos um aspecto, e melhor ou igual a X em todos os outros. Quando essa condição vale, nós dizemos que o hotel X é dominado pelo hotel Y.

Sua tarefa é fazer essa análise: dada uma lista de hotéis, e suas características, remova da lista todos os hotéis que são dominados por algum outro hotel da lista.

Entrada

A entrada possui múltiplos casos de teste. Cada caso de teste começa com uma linha contendo um único inteiro N, que representa o número de hotéis (0 < N ≤ 1000).

Em seguida, há N linhas, cada uma das quais descreve um hotel. Essas linhas possuem 4 campos. O primeiro é o nome do hotel, que é uma string que possui entre 1 e 20 caracteres (inclusive), que podem ser apenas letras (minúsculas ou maiúsculas), dígitos ou hífen (-). Os próximos três campos são inteiros D, P e Q, que representam a distância à praia, preço e qualidade.

D é a distância a praia em metros (0 < D ≤ 4096, quanto menor a distância, melhor);
P é o preço, em reais, da diária do hotel (0 < P ≤ 5000, quanto menor o preço, melhor);
Q é a qualidade do hotel, em número de estrelas (0 < Q ≤ 5, quanto mais estrelas melhor).

A entrada termina com N=0.

Saída

Para cada caso de teste, imprima o nome de todos os hotéis que não são dominados por nenhum outro hotel no mesmo caso de teste. Cada hotel deve ser impresso em uma linha separada, e eles devem ser impressos na mesma ordem em que aparecem na entrada. Após cada caso de teste (inclusive o último) imprima uma linha contendo um único asterisco (*).

Exemplos

Entrada:
3
HotelA 200 160 4
HotelB 400 160 3
HotelC 100 560 5
4
hotel-03 100 300 5
hotel-02 100 400 4
hotel-01 900 100 3
hotel-00 100 300 5
0

Saída:
HotelA
HotelC
*
hotel-03
hotel-01
hotel-00
*