Description

The board is divided into many regions, and each region can contain multiple pieces.

One specific region is numbered $0$. The consecutive regions to its left are numbered $-1,-2,-3,\ldots,$ and the consecutive regions to its right are numbered $1,2,3,\ldots,$. If region $P$ contains pieces, then a piece can be moved in two ways:

• Jump left: add one piece to each of regions $P-1$ and $P-2$, and remove one piece from region $P$.

• Jump right: remove one piece from each of regions $P$ and $P+1$, and add one piece to region $P+2$.

For any given initial position, after some number of jumps, you can always reach a target position where the number of pieces in any two adjacent regions differs by at most $1$.

Your task is: given an initial position, find the final target position.

Input Format

The first line contains a positive integer $n$, which is the number of regions that initially contain pieces.

The next $n$ lines each describe one region, consisting of two integers separated by a space. The first integer is the index of the region (not exceeding $10^4$), and the second integer is the number of pieces in that region (not exceeding $10^8$).

Output Format

Output the final position in one line containing several integers. Each integer is the index of a region that contains pieces, and all region indices must be printed in increasing order.

2
0 5
3 3

-4 -1 1 3 5

Hint

For $100\%$ of the testdata, $1 \le n \le 10^4$.

Translated by ChatGPT 5