该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

徐老师最近有点嘴馋，想去吃一顿金拱门，但是他又想减肥

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

他打算随机生成一个数组，如果这个数组的形状能形成一个 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$

输出格式

对于每个数组判断这个数组能否组成 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!