3864. 打字机

单点时限: 1.0 sec

内存限制: 512 MB

Cuber QQ 长期在网络上与他人对线,一天,他发明了一台神奇的打字机。这台打字机只能处理由 a,b,X 构成的字符串。具体来说,打字机能够执行如下三种操作。

  • 操作$1$:将任意一个 X 替换为 aX
  • 操作$2$:将任意一个 X 替换为 aXbX
  • 操作$3$:删除任意一个 X

打字机启动时,屏幕上有且仅有一个 X

现在 Cuber QQ 想要打出一个仅包含 a , b 的字符串 $s$ 。但是他有选择困难症,注意到,操作 $1$ 和操作 $2$ 都能生成字符 a 。如果 $s$ 中的某个 a 既可以通过操作 $1$ 得到,又可以通过操作 $2$ 得到,Cuber QQ 就会因为难以抉择而不快乐。

Cuber QQ 为了向你详细说明这一点,他决定把操作 $1$ 生成的 a 标记为 $a_1$ ,把操作 $2$ 生成的 a 标记为 $a_2$ 。在这种表示下,Cuber QQ 是否快乐等价于通过各种操作方式(如果存在)生成的字符串 $s$ 是否完全一样。

现在 Cuber QQ 把这个字符串 $s$ 告诉你,请你告诉他,他是否能成功打出这个字符串,如果能够打出这个字符串,你还要告诉他,他是否快乐。

输入格式

本题有多组测试数据,第一行包含一个整数 $T$ ($1\le T\le 10^5$)

之后 $T$ 行,每行是一个仅包含 a , b 的字符串 $s$ ($1\le |s|\le 10^6$)

数据保证所有字符串的长度之和 $\sum |s|\le 10^6$ 。

输出格式

输出 $T$ 行,分别对应每组数据。

如果Cuber QQ可以打出这个字符串,并且开心,输出 Happy Fang

如果Cuber QQ可以打出这个字符串,但不开心,输出 Sad Fang

如果Cuber QQ无法打出这个字符串,输出 Dead Fang

样例

Input
3
ab
aab
baa
Output
Happy Fang
Sad Fang
Dead Fang

提示

第一组数据可以通过如下方式生成: $X \Rightarrow aXbX \Rightarrow abX \Rightarrow ab$ ,且 a 只能通过操作 $2$ 得到。

对于第二组数据,最终可能包含两种不同的下标: $X \Rightarrow a_1 X \Rightarrow a_1 a_2 XbX \Rightarrow a_1 a_2 bX \Rightarrow a_1 a_2b$ 和 $X \Rightarrow a_2XbX \Rightarrow a_2a_1XbX \Rightarrow a_2a_1Xb \Rightarrow a_2a_1b$ 。

对于第三组数据,Cuber QQ 的打字机无法打出这个字符串。

676 人解决,845 人已尝试。

737 份提交通过,共有 3921 份提交。

2.0 EMB 奖励。

创建: 1 年,3 月前.

修改: 1 年,3 月前.

最后提交: 4 天,23 小时前.

来源: N/A

题目标签