字符串游戏

【题目描述】

游戏分为$k$轮，参与者共有$2$个。 给定一个由小写英文字母组成的字符串的集合$S$，在每轮游戏开始时，会有一个空串，然后两人轮流在该串的末尾添加字符，并且需要保证新的字符串是$S$中某个串的前缀，直到有一方不能操作，则不能操作的一方输掉这一轮。 新的一轮由上一轮输的人先手，最后一轮赢的人获得游戏胜利。 假定双方都采取最优策略，求第一轮先手的一方能否获胜。

【输入】

输入包含多组数据，对于每组数据： 第一行包含两个整数$n,k$，分别表示字符串的数量和游戏的轮数。 接下来$n$行，每行包含一个由小写英文字母组成的字符串。

【输出】

对于每组数据输出一行，若先手能获胜输“HY wins!”，否则输出“Teacher wins!”。

【输入样例】

2 3
a
b
3 1
a
b
c
1 2
ab

【输出样例】

HY wins!
HY wins!
Teacher wins!

【提示】

【数据规模与约定】 对于40%的数据，$1≤n≤10，1≤k≤10^4$； 对于100%的数据，$1≤n≤10^5，1≤k≤10^9$，保证所有字符串长度不超过$10^5$，数据组数不超过$10$组。