Реп'яхи

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