Пробіг#6033
Щороку Джо та його друзі хочуть відвідати місцевий ярмарок в Ерлангені, який називається Bergkirchweih. Цього року вони хочуть влаштувати Kastenlauf (перегони з ящиком). Вони стартують з дому Джо і мають одну коробку (Kasten) води (з пляшками). Оскільки вони дуже спраглі, вони випивають одну пляшку води кожні метрів.
Оскільки шлях від дому Джо до Bergkirchweih досить довгий, їм потрібно більше води, ніж вони мають спочатку. На щастя, по дорозі є магазини, де продають воду. Відвідуючи магазин, вони можуть здати порожні пляшки і купити нові, але загальна кількість повних пляшок не може перевищувати (бо їм занадто лінь нести більше, ніж одну повну коробку).
Вам задано координати магазинів, дому Джо та місця проведення Bergkirchweih. Напишіть програму, яка визначить, чи можуть Джо з друзями щасливо дістатися до Bergkirchweih, чи залишаться вони без води дорогою.
У першому рядку вказано кількість тестів (t \leq 50). Кожен тест починається з рядка, що містить число (0 \leq n \leq 100) — кількість магазинів, де продається вода. Наступні n + 2 рядки містять (у цьому порядку) координати дому Джо, магазинів і місця проведення Bergkirchweih. Локацію задано у вигляді двох цілих координат та (обидві в метрах, -32\,768 \leq x, y \leq 32\,767). Оскільки Ерланген має прямокутне планування, відстань між двома локаціями — це сума абсолютних різниць їхніх координат (також відома як манхеттенська метрика).
Для кожного тесту виведіть один рядок: happy (якщо Джо з друзями можуть щасливо дістатися до Bergkirchweih), або sad (якщо вони залишаться без води по дорозі).
Приклад 1