Мости
Дано два опуклих багатокутники, кожен з яких спочатку має N вершин. Один багатокутник розташований строго вище осі OX, інший — строго нижче. З кожного багатокутника по черзі видаляються вершини.
Потрібно визначити довжину найкоротшого відрізка, що з'єднує вершину одного багатокутника з вершиною іншого, перед кожним видаленням вершини та після останнього видалення. Відрізок не повинен проходити через внутрішню область жодного з багатокутників.
Вхідні дані
Перший рядок містить число N (3 ≤ N ≤ 100000) — кількість вершин у кожному багатокутнику. Далі йдуть N рядків, кожен з яких містить два цілих числа: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, 1 ≤ y_{i }≤ 1000000000) — координати вершин першого багатокутника.
Потім йдуть N рядків, кожен з яких містить два цілих числа: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, -1000000000 ≤ y_{i }≤ -1) — координати вершин другого багатокутника. Вершини обох багатокутників перелічені в порядку обходу проти годинникової стрілки. Гарантується, що жодні дві вершини не збігаються, і жодні три вершини одного багатокутника не лежать на одній прямій. Далі йдуть 2N-2 рядків, кожен з яких містить два цілих числа: n_j і v_j (1 ≤ n_j ≤ 2, 1 ≤ v_j ≤ N) — це означає, що потрібно видалити вершину номер v_j з n_j-го багатокутника. Гарантується, що жодна вершина не буде видалена двічі, і що після 2N-2 видалень у кожному з багатокутників залишиться рівно по одній вершині.
Вихідні дані
Виведіть 2N-1 рядок, у кожному з яких одне дійсне число d_j — мінімальна довжина відрізка, що з'єднує вершини двох багатокутників і не проходить через внутрішню область багатокутників. d_j відповідає довжині потрібного відрізка перед j-им за порядком видаленням, d_{2N-1} відповідає довжині потрібного відрізка після всіх видалень. Усі довжини повинні бути точними з абсолютною або відносною похибкою 10^{-8}.