Driving Practice

Sieun, who holds a license that has never been used on the road, practices driving on a number line. Sieun starts at the origin and always moves in the positive direction. The car uses 1 kWh of electricity for each unit of distance it travels, and moving is the only way it uses electricity. The car starts with no electricity, and a car with no electricity cannot move until it is charged.

There are $N + 1$ charging stations, numbered from 0 to $N$, on the number line. Station $i$ is at point $A_i$, and visiting it charges the car by $F_i$ kWh. One of the stations other than station 0 has a mischievous wizard hidden at it. When Sieun arrives at that station, the wizard teleports Sieun to one of the stations that come before it (that is, closer to the origin). Sieun chooses which station to teleport to. Teleporting uses no electricity, and the wizard plays this trick only once.

The car cannot be charged at the station where the wizard plays the trick. After being teleported, Sieun can charge at the stations again. For example, suppose Sieun meets the wizard at station 3 and chooses to teleport to station 1. Then the car can be charged in this order: 0 to 1 to 2 to (no charge at station 3 because of the wizard) to 1 to 2 to 3 to ...

Assume Sieun meets the wizard at each station in turn. Find which station Sieun should choose so that the car runs out of electricity as far from the origin as possible.

The first line contains $N$, the number of charging stations excluding station 0.

Each of the next $N + 1$ lines contains the information for station $i$, in order of increasing number from station 0: $A_i$ and $F_i$, separated by a space.

Print $N$ lines in total. On line $i$, print two integers $x_i$ and $y_i$ separated by a space ($1 \le i \le N$).

If station $i$ cannot be reached without meeting the wizard:

• $x_i$ and $y_i$ are both -1.

Otherwise:

• $x_i$ is the number of the station Sieun should choose when meeting the wizard at station $i$.
• $y_i$ is the change in the electricity stored in the car when Sieun teleports to station $x_i$ and then returns to station $i$.
• If several values of $x_i$ satisfy the condition, print the largest one.

• $1 \le N \le 200{,}000$
• $A_0 = 0$
• $A_0 < A_1 < A_2 < \cdots < A_N \le 10^{12}$
• $1 \le F_i \le 10^6$ ($0 \le i \le N$)
• The car can be charged with an unlimited amount of electricity.
• All input numbers are integers.