Description

Nina and Emilija play a game on paper. At the beginning, the paper is blank. In one turn, a player appends one letter to the end of the current word on the paper. Then they alternate turns. Nina moves first.

When choosing a letter, players must follow this rule: after each added letter, the resulting word must be a prefix of some word in that player’s favorite song. If a player cannot make a move on her turn, she loses.

Assuming both players play optimally, determine who wins.

Input Format

The first line contains a positive integer $n$, the number of words in Nina’s favorite song.

The next $n$ lines each contain one word from Nina’s favorite song.

The next line contains a positive integer $m$, the number of words in Emilija’s favorite song.

The next $m$ lines each contain one word from Emilija’s favorite song.

All input words contain only lowercase letters, and the total length of all words does not exceed $200000$.

Output Format

Output the winning player, Nina or Emilija.

2
aaa
bbb
3
aab
aba
bbb

Nina

2
acg
beh
2
adi
bfj

Emilija

3
ja
sam
vlak
5
sto
zgazit
ce
te
mali

Nina

Hint

Explanation of Sample 1

If Nina first writes the letter b, then Emilija will be forced to write b, and then Nina will continue by writing b. The current word becomes bbb, and Emilija cannot make the next move, so Nina wins.

If Nina first writes the letter a, then Emilija will write b. The word becomes ab, so Nina cannot make the next move, and she loses.

Constraints

For the $40$-point testdata, the total length of all words does not exceed $2000$.

For $100\%$ of the testdata, the total length of all words does not exceed $200000$.

Notes

This problem’s scoring follows the original COCI problem setting, with a full score of $70$.

Translated from COCI2020-2021 CONTEST #3 T2 Vlak.

Translated by ChatGPT 5