Реп'яхи

Limits: 2 sec., 256 MiB

Щороку одного і того ж дня на нашій планеті трапляється якесь диво. Як ви думаєте, коли саме? Якщо ви подумали про 47-ий день року, то ви праві!

Одного такого дня Гордій з Василиною, які живуть у двовимірному просторі, гуляли передмістям. Аж раптом пішов дощ. Але не простий — реп’яховий. Від здивування Василина запропонувала Гордію визначити, як з’єднаються реп’яхи після такого дощу.

Як відомо — реп’яхи липкі. Тому, коли реп’ях торкається якогось іншого реп’яха — він відразу ж зупиняється і приклеюється до нього. Реп’яхи падають один за одним з дуже великої висоти. Коли реп’ях торкається землі — він теж зразу зупиняється. Зверніть увагу, що якщо реп’ях доторкнеться до іншого реп’яха лише боком — він продовжить падати повз.

Вам відомо, що всього падає $n$ реп’яхів у заданому порядку. Кожен реп’ях є ідеальним кругом з радіусом $r_i$. Також відомо, що центр реп’яха завжди знаходиться у координаті $x_i$ і він падає з дуже великої висоти. Допоможіть Гордію визначити координати центрів усіх реп’яхів після дощу.

Input

У першому рядку задано одне ціле число $n$ — кількість реп’яхів.

У наступних $n$ рядках задано пари цілих чисел $x_i$ та $r_i$, які описують реп’яхи в тому порядку, у якому вони падають.

Output

Для кожного реп’яха виведіть по одній парі координат — центри реп’яхів після падіння.

Відносна або абсолютна похибка не повинна перевищувати $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