In Formula One races there is always a high pole next the finish line of the track. Before a race starts, the pole is used to display the starting grid (what car starts at what position). The number of the first car in the grid (the pole position) is displayed at the top of the pole, the number of the car in the second place is shown below the first one, and so on. During the race, the pole is used to display the current position of each car: the car that is winning the race has its number displayed at the top of the pole, followed by the car that is in second place, and so on.

Besides showing the current position of a car, the pole is also used to display the number of positions the cars have won or lost relative to its position on the starting grid. This is done by showing an integer next to the car number. A positive value $$p$$ next to a car number on the pole means that the car has won $$p$$ positions relative to its position on the starting grid. A negative value $$-p$$ means that the car has lost $$p$$ positions. A zero next to a car number on the pole means that the car neither won nor lost any positions (the car is at the same position it started the race).

Given the information displayed on the pole during a Formula One race, you are asked to reconstruct the positions of the cars on the starting grid. While doing this you should take into account that the pole system might not be working properly, causing it to display inconsistent information that makes it impossible to compute valid starting positions for each of the cars. Your program should be able to detect such defects of the pole.

Assignment

Write a function startgrid that takes a list of tuples, where each tuple $$(w, p)$$ describes the position of a car during the race. $$w \in \mathbb{Z}$$ indicates the car number (each car has been assigned a unique number), and $$p \in \mathbb{Z}$$ indicates the number of positions the car has won or lost relative to its position on the starting grid. The order of the tuples in the list determines the current position of the cars during the race. The function should return a list that gives the positions of the cars on the starting grid. This list should contain the car numbers, ordered from the first position to the last position on the starting grid. The function should return an empty list if it is not possible to reconstruct a valid position on the starting grid for any of the cars.

Example

Click the icons next to the examples to see a graphical representation of the position of the cars during the race and the information displayed on the pole at that moment. Use this information to reconstruct the position of the cars on the starting grid.

>>> startgrid([(1, 0), (3, 1), (2, -1), (4, 0)])  
[1, 2, 3, 4]
>>> startgrid([(2, 2), (8, 0),(5, -2), (7, 1), (1, 1), (9, 1),(3, -3)])  
[5, 8, 2, 3, 7, 1, 9]
>>> startgrid([(22, 1), (9, 1), (13, 0), (21, -2)])  
[]
>>> startgrid([(19, 1), (9, -99), (17, 0)])  
[]