P5940 [POI 1997] Jump

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

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.

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 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.

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