Очищення труб
Лінчепінг має досить складну систему водопостачання. Навколо міста розташовані кілька колодязів, з яких видобувається вода. Вода транспортується до різних місць через труби. Кожна труба є прямим каналом від одного з колодязів до певного місця в місті.
Всі труби прокладені на одній глибині під землею. Тому, коли дві труби перетинаються, утворюється перехрестя. На щастя, система трубопроводів спроектована так, що в кожному перехресті зустрічаються рівно дві труби. Колодязі не вважаються перехрестями. До кожного колодязя може прилягати будь-яка кількість труб (включаючи нуль або більше двох).
Перехрестя створюють проблему, оскільки бруд (суміш вапна та інших елементів) має тенденцію накопичуватися там. Цей бруд призводить до розкладання і руйнування труб, що викликає утворення великих провалів. Такі провали мають гіпнотичний ефект на студентів у Лінчепінгу, змушуючи їх нехтувати навчанням, що врешті-решт може призвести до краху не лише трубопровідної системи, але й суспільства в цілому. Тому необхідно регулярно чистити труби. Компанія Nordic Water Extraction and Redistribution Company (NWERC), яка відповідає за водопровідні труби Лінчепінга, має достатньо роботів для виконання цього завдання. Робот може бути вставлений у колодязь, звідки починається труба. Потім він проходить через трубу до кінця, очищаючи всі перехрестя на шляху. Досягнувши кінця, робот повертається назад у колодязь, звідки почав. Щоб уникнути зіткнень роботів, урядові постанови передбачають, що на перехресті двох труб одночасно може перебувати робот лише в одній з них.
Оскільки вся система водопостачання повинна бути відключена під час очищення (згідно з урядовими регулюваннями), NWERC хоче швидко виконати очищення, використовуючи одну партію роботів, які починають роботу одночасно.
Вам потрібно визначити, чи можливо це зробити, тобто чи можна одночасно запустити роботів у певний набір труб так, щоб вони очистили всі перехрестя без ризику зіткнення.
Вхідні дані
Складаються з:
рядка, що містить два числа w (1 ≤ w ≤ 1000) - кількість колодязів, і p (1 ≤ p ≤ 1000) - кількість труб;
w рядків, де i-ий рядок містить два цілі числа
x[i]іy[i](-10000 ≤x[i],y[i]≤ 10000) - координати колодязя номер i (колодязі пронумеровані від 1 до w);p рядків з трьома цілими числами s (1 ≤ s ≤ w) - номер колодязя, з якого починається труба, і x і y (-10000 ≤ x, y ≤ 10000) - координати кінця труби.
Кожна труба починається з одного колодязя. Будь-яка точка, до якої прилягає більше ніж дві труби, є колодязем. Будь-які дві труби мають не більше однієї спільної точки. Спільна точка двох труб може бути кінцевою точкою однієї або обох з них. Всі труби мають позитивну довжину.
Вихідні дані
Якщо можливо почистити всі перехрестя, виведіть "possible". Інакше виведіть "impossible".