题目背景

乃敢与君绝，山高水长路。

往事如烟逝，今朝泪满目。

君心若不悔，何故断情愫？

他日若重逢，唯愿共白头。

题目描述

月老有一个长度为 $n$ 的序列 $a$ 和一个质数 $p$。

你需要找到序列中一个长度至少为 $\frac{n}{2}$ 的子序列。使得该子序列是一个模 $p$ 意义下的等比数列。如果你找不到这样的子序列，你需要输出 Sad.，否则输出两行，第一行为 Happy.，第二行为你选择的子序列的最长的长度。

小 T 有 $T$ 次机会，只有全答对了他才会真正的开心，如果他不开心你就无法得到这个测试点的分数。

形式化的，每组测试数据，对于序列 $n$ 和质数 $p$，判断是否存在长度为 $m(m\geq \frac{n}{2})$ 的子序列 $b$，有定值 $q(1\leq q\lt p)$ 满足 $\forall i\in [2,m],b_i\equiv q\times b_{i-1}\pmod p$。如果存在找出最大可能的 $m$。

特殊的日子，特殊的人，特殊的 P1111 的题号。

输入格式

第一行，一个整数 $T$，表示本测试点的测试数据个数。满足 $1\leq T\leq 10^4$。

接下来有 $T$ 组测试数据。

• 每组测试数据第一行是 $2$ 个整数 $n,p$。满足 $2\leq n\leq 2\times 10^5$，$2\leq p\leq 10^9+7$。保证 $p$ 是质数。

• 接下来一行 $n$ 个正整数，表示序列 $a$。满足 $\forall i\in[1,n],1\leq a_i\lt p$。

保证 $1\leq \sum n\leq 2\times 10^5$，即所有测试数据的 $n$ 之和不会超过 $2\times 10^5$。

输出格式

对于每组测试数据，若不存在长度至少为 $\frac{n}{2}$ 的子序列，输出 Sad.，否则输出两行，第一行为 Happy.，第二行为你选择的子序列的最长的长度。

4
6 1000000007
1 1 2 4 8 16
6 1000000007
597337906 816043578 617563954 668607211 89163513 464203601
5 1000000007
2 4 5 6 8
5 1000000007
2 4 5 6 7

Happy.
5
Sad.
Happy.
3
Sad.

提示

在样例 $1$ 中，对于第一组测试数据，可以选择子序列 $[1,2,4,8,16]$，此时有 $q=2$。

对于 $40\%$ 的数据，满足 $1\leq n\leq 20$；

对于 $60\%$ 的数据，满足 $1\leq n\leq 3000$；

对于 $100\%$ 的数据，满足 $1\leq n\leq 2\times 10^5$，$1\leq \sum n \leq 2\times 10^5$，$2\leq p\leq 10^9+7$。