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

Обмеження: 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)\).