Діаграма Вороного
На площині потрібно обробити Q запитів двох типів:
1 x_i y_i — додати на площину точку (x_i, y_i+dy).
2 x_i y_i — знайти відстань від точки (x_i, y_i+dy) до найближчої точки, яка була додана запитами першого типу.
dy=[last_res] mod 2 — це результат останнього виконаного запиту другого типу, а а[] означає округлення до найближчого цілого. До виконання хоча б одного запиту другого типу, dy=0.
Вхідні дані
У першому рядку задано одне число Q (1 ≤ Q ≤ 200000) — кількість запитів. Далі йдуть Q рядків, кожен з яких містить три цілі числа: t_i, x_i і y_i (1 ≤ t_{i} ≤ 2, 0 ≤ x_i, y_{i} ≤ 1000000) — тип запиту та координати точки. Гарантується, що для всіх 1 ≤ i ≤ Q-1 виконується x_{i} ≤ x_i+1, а також, що всі введені точки різні, навіть з урахуванням модифікації dy. Гарантується, що перший запит завжди є запитом першого типу. Гарантується, що не виникне невизначеностей округлення, тобто дробові частини результатів усіх запитів відрізняються від 0.5 хоча б на 10^{-7}.
Вихідні дані
Для кожного запиту другого типу виведіть в окремому рядку одне дійсне число — відстань від введеної модифікованої точки до найближчої з тих, які на цей момент були додані запитами першого типу. Потрібно, щоб значення були точними з абсолютною або відносною похибкою 10^{-8}.