Stadion

Cesarstwo Bajtockie z powodu deficytu budżetowego poszukuje nowych źródeł dochodu. Dlatego Cesarz Bajtazar zaczął obstawiać wyniki na wyścigach rydwanów. Jednak nie zna się na wyścigach i przegrywa państwowe pieniądze. Wyznaczył więc Bajtoklesowi zadanie przewidzenia wyników wyścigu.

Zawody odbywają się na stadionie, w którym znajduje się zamknięty tor (pętla), po której jeżdżą rydwany napędzane silnikami parowymi. Wzdłuż toru umieszczone są stacje – z każdej z nich startuje jeden pojazd. Wszystkie pojazdy jeżdżą w jednym kierunku, a gdy skończy się paliwo, zatrzymują się. Aby prawidłowo obstawić wynik, cesarz musi znać końcowe pozycje rydwanów – czyli numer ostatniej stacji, przez którą pojazd przejechał zanim się zatrzymał. Stacje numerowane są od 1.

Przed wyścigiem Bajtokles obejrzał rydwany i na podstawie ich konstrukcji (np. wielkość zbiornika z wodą) dla każdego wyznaczył odległość, jaką przejedzie. Pomierzył także odległości między kolejnymi stacjami na torze. Mając te dane, wyznacz końcowe pozycje pojazdów.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczby całkowita N (1<=N<=5*10^5) oznaczająca liczbę stacji.
W kolejnych N wierszach znajdują się opisy stacjii i rydwanów: w (i+1) wierszu są dwie liczby całkowite
Zi (0<=Zi<=10^9) – odległość jaką przejedzie pojazd startujący z i-tej stacji
Di (0<=Di<=10^9) – odległość i-tej stacji od następnej stacji
Ostatnia podana odległość to odległość pomiędzy ostatnią a pierwszą stacją (tor jest pętlą).

Wyjście

Twój program powinien wypisać N wierszy. W i-tym wierszy powinna znajdować się jedna liczba całkowitą: numer ostatniej stacji, przez którą przejechał pojazd startujący z i-tej stacji. Jeśli nie dojechał do żadnej innej stacji, należy wypisać i.

Przykład

Dla danych wejściowych:
5
12 5
3 2
7 5
4 4
1 3

poprawną odpowiedzią jest:
4
3
4
5
5