说明

蒟蒻队长最近有点嘴馋，想去吃一顿金拱门，但是他又想减肥

于是他决定给自己一个机会，把命运交给计算机！

他打算随机生成一个数组，如果这个数组的形状能形成一个 `M`，那么他就去吃麦当劳，如果不能就不去

蒟蒻队长认为，对于一个长度为 $n$ 的整数数组 $a$ 来说，只要存在一组 $1 < x < y < z < n$ 满足以下条件

1. $a_1 < a_2 < ... < a_x$
2. $a_x > a_{x+1} > a_{x+2} > ... > a_y$
3. $a_y < a_{y+1} < a_{y+2} < ... < a_z$
4. $a_z > a_{z+1} > a_{z+2} > ... > a_n$

那么这个数组就能形成 `M`，蒟蒻队长就可以去吃金拱门啦！

输入格式

输入第一行包含两个整数 $T,n$，表示蒟蒻队长生成了 $T$ 个长度为 $n$ 的数组

接下来每一行包含 $n$ 个整数，表示一个长度为 $n$ 的数组

数据编号	$n$
$1 \sim 2$	$n \leq 50$
$3 \sim 4$	$n \leq 200$
$5 \sim 6$	$n \leq 1000$
$7 \sim 8$	$n \leq 10^5$
$9 \sim 10$	$n \leq 3 * 10^5$

对于所有数据满足：$T \leq 10, 1 \leq a_i \leq 10^9$

</span>

输出格式

对于每个数组判断这个数组能否组成 `M`，若能组成请输出 `Havefun!`，若不能请输出 `Sad!`

2 11
1 2 3 4 3 2 3 4 3 2 1
9 8 7 6 7 8 9 10 9 8 7

Havefun!
Sad!

来源

CSP模拟赛