만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Prijateljice

면접 대비

시간 제한1초메모리 제한1024 MB

요약
두 사람이 번갈아 자기 목록에서 사전순으로 더 큰 단어를 말합니다. 다음 단어는 앞 단어와 같은 글자 또는 다음 글자로 시작해야 하며, 레오나가 가장 작은 단어로 시작할 때 승자를 구합니다.
난이도

보통10점 중 5점

유형
게임 이론, 동적 계획법, 정렬
정답자
아직 제출이 없습니다

문제

크르크 섬에서 보낸 어느 여름 밤, 레오나와 조에는 산책을 나갔다. 구불구불한 길에서 두 사람은 단어가 잔뜩 쌓인 더미를 발견했다. 들뜬 둘은 곧바로 단어를 모으기 시작했다. 레오나는 nn개, 조에는 mm개의 단어를 모았다. 한동안 단어를 구경한 뒤 두 사람은 다음 게임을 하기로 했다.

한 번의 차례에 플레이어는 자신의 더미에서 단어 하나를 말한다. 이때 단어는 두 조건을 모두 만족해야 한다. 직전 단어보다 사전순으로 커야 하고, 직전 단어와 같은 글자로 시작하거나 직전 단어의 첫 글자 바로 다음 영문 알파벳으로 시작해야 한다. 차례에 단어를 말하지 못한 플레이어는 진다.

두 사람은 번갈아 차례를 진행하며, 레오나가 사전순으로 가장 앞선 자신의 단어를 말하면서 먼저 시작한다. 두 사람이 최선을 다한다면 누가 이기는지 구하라.

참고: 단어 A가 단어 B의 접두사이거나, 두 단어가 처음 다른 위치에서 A의 글자가 B의 글자보다 앞에 있으면 A는 B보다 사전순으로 작다.

입력

첫 줄에 정수 nn과 mm이 주어진다 (1≤n,m≤1051 \le n, m \le 10^5). 레오나의 단어 nn줄이 이어지고, 그 다음에 조에의 단어 mm줄이 주어진다.

단어는 영어 소문자로만 이루어지며, 모든 단어는 서로 다르다. 단어 길이의 총합은 10610^6 이하이다. 레오나의 단어와 조에의 단어는 각각 사전순으로 정렬되어 있다.

출력

이긴 사람의 이름 Leona 또는 Zoe를 출력한다.

힌트

첫 번째 예제에 대한 설명이다. 레오나가 avokado로 시작하면 조에는 가진 단어 brazil 하나로 이어간다. 레오나는 더 이상 말할 단어가 없어서 진다.

예제3

  1. 예제 1

    입력
    2 1
    avokado
    dabar
    brazil
    
    예상 출력
    Zoe
    
  2. 예제 2

    입력
    3 3
    ananas
    atlas
    banana
    albatros
    cikla
    nogomet
    
    예상 출력
    Leona
    
  3. 예제 3

    입력
    2 2
    hrvatska
    zastava
    bijeli
    galeb
    
    예상 출력
    Leona