Runda 19 [Hard] - Robaki reaktywacja

02.05.2011 - Damian Rusak

Zadanie tygodnia

runda 19; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 32MB

Robaki reaktywacja

Czy pamiętacie zadanie Robaki z Zawodów Stałych? Tym razem stoimy przed trudniejszym zadaniem!

Na pręcie długości $L$ umieszczono w pewnych miejscach wiele robaczków. Każdy z nich ma określony kierunek poruszania się - w kierunku lewego końca pręta, lub w kierunku prawego końca pręta. Każdy porusza się z tą samą stałą prędkością.

Robaczki są całkiem masywne (choć rozmiarem równe punktowi!) i gdy dwa spotkają się na pręcie idąc w przeciwne strony, oba w mgnieniu oka zmieniają kierunki - tak, jakby odbiły się od siebie. Jeśli jakiś robak dotrze do lewego lub prawego końca pręta, spada zeń i nie ma już po nim śladu.

Zadanie, jakie nasuwa się szybko - znająć początkowe położenia robaczków na pręcie i kierunki, w których zmierzają, odpowiedz, który z nich spadnie z pręta jako ostatni? Możesz założyć, że dane będą dobrane w ten sposób, że nie dojdzie do sytuacji, w której kilka robaków spadałoby w ostatniej chwili.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby - $n$ oraz $L$ - odpowiednio liczbę robaków oraz długość pręta ( $1 \leq n \leq 10^{5}$ , $1 \leq L \leq 10^{9}$ ). W kolejnych $n$ liniach znajdują się pary liczb cakowitych $p_{i}$ $k_{i}$ - odpowiednio położenie i kierunek robaczka. Pręt traktujemy jak odcinek $[0,L]$ . Wartość $p_{i}$ oznacza punkt na tym odcinku na którym znajduje się robaczek, za to $k_{i}$ wyznacza kierunek - $k_{i}=0$ mówi, że robaczek zmierza w kierunku punktu $0$ , $k_{i} = 1$ , że w kierunku punktu $L$ . ( $0 \leq p_{i} \leq L$ , $k_{i} \in \left\{0,1\right\}$ ).

Wyjście:

Wyjście powinno zawierać jedną liczbę - numer robaka, który spadnie z pręta jako ostatni. Robaki numerowane są od $1$ do $n$ zgodnie z kolejnością na wejściu.