题目描述

游戏分为$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$组。

完整数据范围与边界约定

输入至文件末尾，共1..10组，不含额外总组数；每组1≤n≤100000，1≤k≤10^9。字符串只含小写字母、非空、单串长度≤100000；所有组全部字符串长度之和≤10^6。允许重复字符串，重复不改变集合；字符串自身若仍是更长词的前缀，则仍可继续操作，只有无合法下一个字符时才输。每轮输者先手下一轮，最终只看第k轮赢家。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：输入至文件末尾，共1..10组，不含额外总组数；每组1≤n≤100000，1≤k≤10^9。字符串只含小写字母、非空、单串长度≤100000；所有组全部字符串长度之和≤10^6。允许重复字符串，重复不改变集合；字符串自身若仍是更长词的前缀，则仍可继续操作，只有无合法下一个字符时才输。每轮输者先手下一轮，最终只看第k轮赢家。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1819。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。