#736. [CZOJ 一周一测 R4 C] 华莱士

[CZOJ 一周一测 R4 C] 华莱士

题目背景

小 H,小 L 和小 S 是朋友,他们在华莱士门口玩一种不是很新的游戏,并约定输的人请赢的人吃华莱士。

题目描述

他们在纸上写下 nn 个随机的正整数,然后按照小 H,小 L,小 S 的顺序进行操作,如果一个人操作完,接下来的人无法继续操作,则那个人就是赢家。 操作为,选择一个大于 11 的数,将它变为它所有质因数的和(如果它是一个质数的话,变为1)。 他们三人都会尽量选择对自己有利的操作方法,问最后谁赢(输出 HLS),或游戏将一直进行下去(输出 draw)。

输入格式

第一行一个整数 nn,接下来 nn 个正整数。

输出格式

一个字符(串)表示答案。

4
1 9 8 1
H

样例解释

一种可能的游戏顺序是:

小 H 选择对 88 进行操作,四个数变为 1 9 2 1.

小 L 选择对 99 进行操作,四个数变为 1 3 2 1.

小 S 选择对 22 进行操作,四个数变为 1 3 1 1.

小 H 选择对 33 进行操作,四个数变为 1 1 1 1.

此时已经没有大于 11 的数,故小 L 无法操作,小 H 获胜。

数据范围

对于所有数据,保证 1n1061 \leq n \leq 10^6,最大的数不超过 10710^7

对于 20%20\% 的数据,保证 n100n \leq 100,最大的数不超过 100100

另有 30%30\% 的数据,保证最大的数不超过 10510^5.