Jumps

Memory limit: 32 MB

“Jumps” is a board game played on an infinite tape of squares. The board has neither left nor right limit. On the squares there is finitely many pieces (more than one piece on a square is allowed). We assume that the most left, non-empty square is numbered . Squares on the right are denoted by consecutive natural numbers , squares on the left — by negative numbers: . The configuration of pieces on the board can be described in the following way: for every square occupied by at least one piece we give the number of the square and the number of pieces standing on this square.

There are two kinds of moves that can change the configuration: jump right and jump left. Jump right consists of removing two pieces from the board: one from a square and the other from the square , and placing one piece on the square . Jump left consists of removing a piece from a square and placing two pieces on the board: one on the square and the other on the square .

We say that a configuration is final if each pair of neighbouring squares contains at most one piece. For every configuration there is exactly one final configuration that can be reached after finite number of moves (jumps).

Task

Write a program that:

• reads a description of an initial configuration from the standard input,
• finds the final configuration that can be reached from the given initial configuration and writes the result to the standard output.

Input

In the first line of the standard input there is one positive integer , , which equals the number of non-empty squares of the given initial configuration.

In each of the following lines there is a description of one non-empty square of the initial configuration. Such a description consists of two integers. First is the number of the square, second — the number of pieces standing on this square. The descriptions are given in increasing order with respect to numbers of squares. The biggest number of a square is not greater than and the number of pieces on a single square is not greater than .

Output

In the first line of the standard output there should be written the final configuration that can be reached from the given initial configuration. More precisely the line should contain the numbers of non-empty squares (in increasing order) of the final configuration. The numbers should be separated by single spaces.

Example

For the input data:

2
0 5
3 3

the correct result is:

-4 -1 1 3 5 

Task author: Bogdan S. Chlebus.