Kosmiczny pościg

Limit pamięci: 32 MB

Bajtoks, galaktyczny awanturnik, znowu wpadł w tarapaty! Ucieka właśnie swoim statkiem kosmicznym przed oddziałem Bitoków.

Na szczęście nie jest sam - bohaterowi towarzyszą na pokładzie: Bajtinoks, operator działa laserowego, i Ty, programista komputera pokładowego. Bitokowie, jako dosyć prymitywna rasa, nie dysponują żadną bronią dalekiego zasięgu, więc będą starali się po prostu dogonić statek Bajtoksa. Bajtinoks jest strzelcem wyborowym i nigdy nie pudłuje, jednak nie wie, w jakiej kolejności ma strzelać do nieprzyjaciół. I to jest właśnie zadanie dla Ciebie!

Napisz program, który obliczy kolejność, w jakiej Bajtinoks powinien strzelać do przeciwników, aby zmaksymalizować szanse ucieczki.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę wrogich statków. W drugim wierszu znajdują się dwie liczby całkowite , oddzielone pojedynczym odstępem (, , oznaczające odpowiednio położenie początkowe i prędkość statku Bajtoksa.

Kolejne wierszy zawiera opisy wrogich statków. Każdy taki opis składa się z dwóch liczb całkowitych , oddzielonych pojedynczym odstępem (, , oznaczających odpowiednio położenie początkowe -tego bitockiego statku oraz jego prędkość. Wszystkie położenia (liczby ) wyrażone są w bajtometrach, a prędkości (liczby ) - w bajtometrach na bajtosekundę. Wszystkie statki poruszają się wzdłuż jednej linii prostej.

Pomiędzy dowolnymi dwoma strzałami Bajtinoksa musi upłynąć co najmniej jedna bajtosekunda, aby zdążył on przeładować działo. W tym czasie każdy statek przemieszcza się o bajtometrów. Jeżeli którykolwiek z wrogich statków znajdzie się podczas tego ruchu na tej samej pozycji co Bajtoks, to bohater przegrywa (chyba że będzie to tylko jeden wrogi statek i zbliży się on dokładnie w momencie, w którym Bajtinoks zakończy przeładowywanie działa - wtedy przeciwnik będzie jeszcze mógł zostać zestrzelony).

Na samym początku pościgu Bajtinoks jest już przygotowany do strzału, więc nie musi przed nim przeładowywać działa.

Zakładamy, że statek Bajtoksa jest na początku najdalej spośród wszystkich statków (czyli dla każdego zachodzi: ), ponadto statki mogą się bez problemu wymijać. Bajtinoks może trafić w dowolny z wrogich statków. Czas przelotu promienia laserowego można pominąć. Jedno trafienie wystarczy, by zniszczyć dowolny statek.

W testach wartych łącznie 50 punktów zachodzi dodatkowo nierówność .

Wyjście

Jeżeli załoga Bajtoksa może zestrzelić wszystkich ścigających, to w pierwszym i jedynym wierszu standardowego wyjścia powinny znaleźć się wszystkie liczby całkowite z przedziału (każda dokładnie raz) pooddzielane pojedynczymi odstępami i oznaczające numery wrogich statków w kolejności, w jakiej Bajtinoks powinien do nich strzelać. Jeśli istnieje wiele możliwych sekwencji strzałów, przy których Bajtoks ucieknie wrogom, Twój program powinien wypisać dowolną z nich.

Jeśli natomiast załoga Bajtoksa skazana jest na porażkę, to w pierwszym i jedynym wierszu wyjścia należy wypisać słowa GAME OVER (oddzielone pojedynczym odstępem).

Przykład

Dla danych wejściowych:

3
5 1
0 2
3 3
-2 3

poprawną odpowiedzią jest:

2 1 3

Wyjaśnienie do przykładu: Strzelamy do trzeciego wroga. Po bajtosekundzie jesteśmy na pozycji 6, wróg pierwszy na pozycji 2, a wróg drugi na pozycji 6. Strzelamy do wroga drugiego, w ostatniej chwili ratując się przed nim. Po drugiej sekundzie jesteśmy na pozycji 7, a wróg pierwszy na pozycji 4, możemy więc spokojnie go zestrzelić i uciec.

Inne poprawne odpowiedzi dla tego testu to: 1 2 3, 2 1 3, 2 3 1.

Autor zadania: Michał Włodarczyk.