Šeštadieninė informatikos olimpiadininkų mokykla

N varžovų sustoja atsitiktinėse stadiono rato vietose. Po starto visi varžovai pradeda bėgti ratu pagal laikrodžio rodyklę. Jei kurį varžovą pasiveja kitas, tai aplenktasis iškrenta iš varžybų. Varžybos baigiasi, kai lieka vienas dalyvis arba nė vienas iš likusiųjų nebegali pavyti kitų. Visi likusieji varžovai tampa nugalėtojais.

Užduotis

Parašykite programą, kuri nustatytų, kuria tvarka iškris varžybų dalyviai ir kas laimės.

Įvestis

Pirmojoje įvesties eilutėje pateiktas dalyvių skaičius N (N ≤ 500 000) bei stadiono vieno rato ilgis L (L < 5 000 000). Kitose N eilučių pateikta informacija apie varžybų dalyvius ta tvarka, kaip jie yra sustoję stadione prieš startą (skaičiuojant nuo starto linijos pagal laikrodžio rodyklę). Apie kiekvieną varžovą nurodoma, kiek jis yra nutolęs nuo starto linijos varžybų pradžioje D (0 ≤ D₁ < D₂ < ... < D_N < L) ir jo greitis S (0 < S_i ≤ 5). Atstumai pateikiami metrais, o greitis – metrais per sekundę.

Išvestis

Pateikite sąrašą dalyvių, kurie iškrito iš varžybų. Sąrašą pateikite tą tvarka, kuria dalyviai buvo eliminuoti. Paskutinėje eilutėje, kuri turi prasidėti tekstu "Winner(s):", pateikite didėjimo tvarka išrikiuotą sąrašą laimėtojų. Laimėtojus sąraše atskirkite tarpu.

Pavyzdžiai

6 150
0 1.75
30 0.80
60 0.50
70 1.00
120 0.10
140 0.90

2
3
5
4
6
Winner(s): 1