You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

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

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

题目描述

月老有一个长度为 $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$。