【题目描述】
游戏分为$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$组。