Background

A checkers-like jumping game is played on an infinitely long board.

Problem 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