# revised by ChatGPT
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
def has_children(self):
return bool(self.children)
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def starts_with(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
def can_win(current_nodes, current_char):
# Fetch Nina's current node based on the character
nina_node = current_nodes[0].children.get(current_char)
# Emilija's current node
emilija_node = current_nodes[1]
# If Nina's node is not valid or has no children, Nina can't continue, so she loses
if not nina_node or not nina_node.has_children():
return False
# Explore all possible moves from the current character
for next_char, next_nina_node in nina_node.children.items():
# If Emilija can't win from this position, Nina wins
if not can_win([emilija_node, next_nina_node], next_char):
return True
# If all possible moves still allow Emilija to win, Nina loses
return False
# Create Trie structures for Nina and Emilija
nina_trie = Trie()
emilija_trie = Trie()
# Insert Nina's favorite words into her Trie
for _ in range(int(input())):
nina_trie.insert(input().strip())
# Insert Emilija's favorite words into her Trie
for _ in range(int(input())):
emilija_trie.insert(input().strip())
# Start the game with Nina's root node linked to the letter 'N'
nina_start = TrieNode()
nina_start.children['N'] = nina_trie.root
# Determine the winner and print the result
print('Nina' if can_win([nina_start, emilija_trie.root], 'N') else 'Emilija')
