Magic Rods

Bella has $n$ numbered magic rods. To get magic energy, Bella lights each rod at both ends, possibly at different moments. The fire spreads at one centimeter per second. The energy of a rod is released at the moment the fire covers the whole rod.

The length of rod $i$ is $l_i$ centimeters. Help Bella choose the ignition times of the ends of each rod so that the energy of all rods is released at the same moment. Bella also wants the last point of rod $i$ to catch fire at distance $d_i$ from the first end of that rod.

All ignition times must be positive integers. Among all valid answers, choose the one that minimizes the moment when all the energy is released.

The first line contains one integer $n$ ($1 \le n \le 10,000$), the number of rods. Each of the next $n$ lines contains two integers $l_i$ and $d_i$ ($2 \le l_i \le 1,000,000$, $0 < d_i < l_i$): the length of rod $i$ and the distance from its first end to the point that must be lit last.

On the $i$-th line, print two positive integers $t_{i1}$ and $t_{i2}$: the moments to ignite the first and the second end of rod $i$.