Once every year, Jo and his friends want to visit the local
fair in Erlangen, called Bergkirchweih. This year, they want to
make a Kastenlauf (box run). They start at Jo’s home, and have
one box (Kasten) of beer (with twenty bottles). As they are
very thirsty, they drink one bottle of beer every 50
As the way from Jo’s home to the Bergkirchweih is pretty
long, they need more beer than they have initially.
Fortunately, there are stores selling beer on the way. When
they visit a store, they can drop their empty bottles and buy
new bottles, but their total number of full bottles will not be
more than twenty (because they are too lazy to carry more than
one full box).
You are given the coordinates of the stores, of Jo’s home
and of the location of the Bergkirchweih. Write a program to
determine whether Jo and his friends can happily reach the
Bergkirchweih, or whether they will run out of beer on the
Input starts with one line containing the number of test
cases $t$ ($t \leq 50$).
Each test case starts with one line, containing the number
$n$ of stores selling beer
(with $0 \leq n \leq
The next $n+2$ lines
cointain (in this order) the location of Jo’s home, of the
stores, and of the Bergkirchweih. The location is given with
two integer coordinates $x$ and $y$, (both in meters, $-32768 \leq x, y \leq 32767$).
As Erlangen is a rectangularly laid out city, the distance
between two locations is the difference of the first coordinate
plus the difference of the second coordinate (also called
For each test case print one line, containing either “happy”
(if Jo and his friends can happily reach the Bergkirchweih), or
“sad” (if they will run out of beer on the way).
|Sample Input 1
||Sample Output 1