Шестикутні палички
Розглянемо нескічннну шестикутну сітку. Сітка складається з однакових правильних шестикутних комірок, рохміщених як показано нижче. На рисунку також подана система координат, яка використовується для ідентифікації кожної комірки. Кожна комірка сітки може бути або порожньою, або заблокованою.
Рисунок: Частина сітки
Декілька паличок поклали довільним чином на сітку. Довжина кожної палички рівна одній "шестикутній одиниці". Це значить, що кінці палички розміщені у центрах сусідніх комірок. Вам потрібно перемістити палички таким чином, щоб отримати замкнений правильний шестикутник.
На рисунках нижче наведено приклади замкнених шестикутників, зроблених з паличок.
Вам задані початкові координати паличок, розміщених на сітці. Також будуть задані координати заблокованих комірок. За один хід можна здійснити одну з наступних операцій:
Виберіть одну паличку і викиньте її
Виберіть одну паличку і поверніть її на 60 градусів за/проти годинникової стрілки навколог одного з її кінців
Виберіть одну паличку і проштовхніть її на довжину палички.
Палички ніколи не повинні займати заблоковані комірки. Проте дві палички можуть займати одну і ту ж комірку одночасно.
Розглянемо стан сітки вище. Перепона знаходиться у комірці з координатами (1, 1), а кінці паличок у комірках (0, 0) - (1, 0). Чотири можливі операції над паличкою подано нижче
По завершенню усіх операцій на сітці повинен утвортись замкнений правильний шестикутник без паличок, що лежать навколо. Це значить, що на сітці знаходиться у точності 6*x паличок, де x - натуральне число. Чи можете Ви зробити це за найменшу кількість операцій?
Вхідні дані
Перший рядок містить кількість тестів T (T < 50). Кожен тест починається з кількості наявних паличок S (S < 9). Наступні S рядків описують координати паличок у форматі x_1 y_1 x_2 y_2, що позначає паличку від (x_1, y_1) до (x_2, y_2). Координати коректні, а довжина кожної палички дорівнює шестикутній одиниці, як вказано вище. У наступному рядку задається кількість перепон B ( B < 20). Кожен з наступних B рядків задає координати перепон. Координати мають формат x_1 y_1. Гарантується, що перепони не перетинаються з жодною з паличок. Усі координати (паличок та перепон) лежать у проміжку [-4, 4].
Примітка: Пам'ятайте, що ми маємо справу з нескінченною сіткою. Тому у відповіді координати паличок можуть лежати поза проміжком [-4, 4].
Вихідні дані
Для кожного тесту вивести його номер, за яким йде найменша кількість потрібних операцій. Якщо сфорувати шестикутник з паличок неможливо, то вивести "impossible". Дотримуйтесь наведеного формату вхідних та вихідних даних.