#P3901. 「COCI 2022.12」Prijateljice

「COCI 2022.12」Prijateljice

题目描述

译自 COCI 2022/2023 Contest #2 T4「Prijateljice

在克尔克的一个夏天晚上,Leona 和 Zoe 去散步。在散步路上,她们发现了一堆单词!她们十分激动并且迅速收集了这些单词:Leona 收集了 nn 个,Zoe 收集了 mm 个。在欣赏了一会儿之后,她们决定用这些单词玩一个游戏:

在一轮中玩家说出她的词堆中的一个单词。玩家按满足如下条件的方式选择单词:这个单词的字典序比之前的单词大,并且要么这个单词的开头字母与之前单词的开头字母相同,要么这个单词的开头字母是上个单词开头字母在英语字母表中的下一个。如果玩家在一轮中不能说出单词,那么她就输了。

她们交替在每轮中说单词,Leona 首先说出她词堆中字典序最小的单词。如果 Leona 和 Zoe 按最优方式进行游戏,确定谁会赢。

注:如果单词 AA 是单词 BB 的前缀,或者对于单词 AABB 不同的第一个字母,单词 AA 的字母在字母表的顺序比单词 BB 的靠前,则称单词 AA 的字典序比单词 BB 小。

输入格式

输入第一行包含两个整数 n,m (1n,m105)n,m\ (1\le n,m\le 10^5),分别表示 Leona 和 Zoe 的单词数。

接下来 nn 行,每行一个字符串,表示 Leona 的单词。

接下来 mm 行,每行一个字符串,表示 Zoe 的单词。

输入中,单词均为仅由小写英文字母构成的字符串,所有单词互不相同,它们的总长度不超过 10610^6,并且 Leona 和 Zoe 的单词均已经按字典序排好序了。

输出格式

输出胜者的名字,LeonaZoe

2 1
avokado
dabar
brazil

Zoe

3 3
ananas
atlas
banana
albatros
cikla
nogomet

Leona

2 2
hrvatska
zastava
bijeli
galeb

Leona

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号 附加限制 分值
11 n,m100n,m\le 100,每个单词最多包含 1010 个字母 1818
22 n,m1 000n,m\le 1\ 000 2727
33 无附加限制 5555