Пробіг
Щороку Джо та його друзі планують відвідати місцевий ярмарок в Ерлангені, відомий як Бергкірхвайх. Цього разу вони вирішили взяти участь у Kastenlauf (забігу з ящиком). Вони починають свій шлях від дому Джо, маючи одну коробку (Kasten) пива з двадцятьма пляшками. Щоб не страждати від спраги, вони випивають одну пляшку пива кожні 50 метрів.
Оскільки шлях від дому Джо до Бергкірхвайха досить довгий, їм знадобиться більше пива, ніж вони взяли з собою. На щастя, на маршруті є магазини, де можна купити пиво. Відвідуючи магазин, вони можуть здати порожні пляшки та придбати нові, але загальна кількість повних пляшок не повинна перевищувати двадцяти (хлопці занадто ледачі, щоб нести більше однієї повної коробки).
Вам надано координати магазинів, дому Джо та місця проведення Бергкірхвайха. Напишіть програму, яка визначить, чи зможуть Джо та його друзі щасливо дістатися до Бергкірхвайха, або ж у них закінчиться пиво на шляху.
Вхідні дані
Перший рядок містить кількість тестів t (t ≤ 50). Кожен тест починається з кількості магазинів n (0 ≤ n ≤ 100), що торгують пивом. Наступні n + 2 рядки містять (у такому порядку) координати дому Джо, магазинів та Бергкірхвайха. Кожне місце задається двома цілими координатами x і y (в метрах, -32768 ≤ x, y ≤ 32767). Оскільки Ерланген має структуру прямокутної сітки, відстань між двома точками визначається як сума різниць координат (Манхеттенська метрика).
Вихідні дані
Для кожного тесту виведіть в окремому рядку або "happy" (якщо Джо та його друзі благополучно досягнуть Бергкірхвайха), або "sad" (якщо у них на шляху закінчиться пиво).