Цукерочки на столі

Обмеження: 6 сек., 1024 МіБ

Після змагань Зеник і Марічка в себе вдома жваво обговорювали задачі та їли цукерочки з друзями. Коли вони наїлися цукерочок досхочу й усі поділилися своїми розв’язки до задач із сьогоднішньої олімпіади, то Марічка придумала ще одну задачу.

Спершу вона розкладає $n$ цукерочок на столі. $i$-у цукерочку Марічка ставить у точку з координатами $(x_i, y_i)$.

Після цього вона робить $q$ дій. Кожна дія — це або поставити ще одну цукерочку на стіл у точку з координатами $(x_j, y_j)$, або забрати останню додану цукерочку. Після кожної дії треба знайти мінімальну відстань між будь-якими двома цукерочками на столі.

Вхідні дані

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

У настуних $n$ рядках задано по два цілих числа $x_i$ та $y_i$ — координати $i$-ої цукерочки.

У наступних $q$ рядках описано дії Марічки. Дія додавання цукерочки на стіл описана рядком 1 $\quad x_j \quad y_j$, а дія забирання останньої доданої цукерочки описана одним числом 0.

Марічка ніколи не буде забирати цукерочки, які початково були на столі, а також ставити цукерочку у вже зайняту координату.

Вихідні дані

Виведіть $q$ дійсних чисел в окремих рядках — відповідь на задачу після кожної дії Марічки. Відповідь уважатиметься правильною, якщо її абсолютна або відносна похибка не перевищує $10^{-7}$.

Обмеження

$2 \le n \le 10^5$,

$1 \le q \le 10^5$,

координати цукерочок невід’ємні та не перевищують $10^6$.

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

9 балів — $n, q \le 10^3$,

15 балів — без додаткових обмежень.

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 5 1 3 4 7 8 3 1 9 8 1 6 4 0 1 4 4 1 6 4	5.000000000 2.236067977 5.000000000 3.000000000 2.000000000

Примітки

Спочатку Марічка ставить три цукерочки в точки з координатами $(1, 3)$, $(4, 7)$ і $(8, 3)$.

Після цього відбуваються п’ять дій.

• Марічка ставить цукерочку в точку $(9, 8)$. Відстань між точками $(1, 3)$ і $(4, 7)$ дорівнює $\sqrt{(4-1)^2+(7-3)^2}=5$. Це найменша відстань серед усіх пар цукерочок на столі.

• Марічка ставить цукерочку в точку $(6, 4)$. Найменша відстань досягається між цукерочками в точках $(4, 7)$ і $(6, 4)$ і дорівнює $\sqrt{5}$.

• Марічка забирає цукерочку з точки $(6, 4)$. Найменша відстань знов досягається між точками $(1, 3)$ і $(4, 7)$ і дорівнює $5$.

• Далі вона ставить цукерочку в точку $(4, 4)$. Тепер найменша відстань — це відстань між точками $(4, 4)$ і $(4, 7)$.

• Після додавання цукерочки в точку $(6, 4)$ мінімальна відстань досягається між точками $(4, 4)$ і $(6, 4)$.