Burdocks

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Every year on the exact same day, a miracle happens on our planet. When do you think that is? If you thought of the 47th day of the year, you are right!

On one such day, Hordiy and Vasylyna, who live in a two-dimensional space, were walking in the suburbs. Suddenly, it started to rain. But not just any rain — burdock rain. Out of surprise, Vasylyna suggested to Hordiy that they determine how the burdocks will connect after such rain.

As you know, burdocks are sticky. Therefore, when a burdock touches another burdock, it immediately stops and sticks to it. Burdocks fall one after another from a very great height. When a burdock touches the ground, it also stops immediately. Note that if a burdock touches another burdock only by its side (tangentially), it will continue falling past it.

You are given that a total of \(n\) burdocks fall in a given order. Each burdock is a perfect circle with radius \(r_i\). It is also known that the center of the burdock is always at coordinate \(x_i\) and it falls from a very great height. Help Hordiy determine the coordinates of the centers of all burdocks after the rain.

Input

The first line contains a single integer \(n\) — the number of burdocks.

The next \(n\) lines contain pairs of integers \(x_i\) and \(r_i\), which describe the burdocks in the order they fall.

Output

For each burdock, output a pair of coordinates — the centers of the burdocks after falling.

The relative or absolute error must not exceed \(10^{-7}\).

Constraints

\(1 \le n \le 1000\),

\(0 \le |x_i| \le 10^6\),

\(1 \le r_i \le 10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 4 2 7 1 8 1	4.0000000 2.0000000 7.0000000 1.0000000 8.0000000 2.7320508

Notes