A. 打字机 - EOJ Monthly 2020.7 Sponsored by TuSimple

仪表盘所有提交榜单题解

单点时限: 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 \leq T \leq 10^{5}$ )

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

数据保证所有字符串的长度之和 $\sum | s | \leq 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 a X b X \Rightarrow a b X \Rightarrow a b$ ，且 a 只能通过操作 $2$ 得到。

对于第二组数据，最终可能包含两种不同的下标： $X \Rightarrow a_{1} X \Rightarrow a_{1} a_{2} X b X \Rightarrow a_{1} a_{2} b X \Rightarrow a_{1} a_{2} b$ 和 $X \Rightarrow a_{2} X b X \Rightarrow a_{2} a_{1} X b X \Rightarrow a_{2} a_{1} X b \Rightarrow a_{2} a_{1} b$ 。

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

NaN

A. 打字机 B. 线上考试 C. OLED D. 前缀排序 E. 因数串

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2020.7 Sponsored by TuSimple

输入格式

输出格式

样例

提示

题目列表

服务

开源

关于我们