COCI '20 Contest 3 #2 Vlak

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Nina and Emilija are playing a game on a piece of paper. Initially, the paper is empty. In one move a player appends a letter to the end of the word that is currently written on the paper. They alternate turns, and Nina plays first.

Players must choose the letters in such a way that the following condition is met: the word that is written after the player's move must be a prefix of some word in that players favourite song. If the player can't make a move, she loses.

If both players play optimally, determine who wins.

Input

The first line contains a positive integer , the number of words in Nina's favourite song. Each of the following lines contains a word from Nina's favourite song.

The following line contains a positive integer , the number of words in Emilija's favourite song.

Each of the following lines contains a word from Emilija's favourite song.

Words in input contain only lowercase letters, and the sum of the lengths of all words is at most .

Output

Output Nina or Emilija, the name of the winner.

Scoring

In test cases worth 40 points the sum of the lengths of the words will be at most .

Sample Input 1

2
aaa
bbb
3
aab
aba
bbb

Sample Output 1

Nina

Explanation for Sample Output 1

If Nina first writes b, Emilija must write b, and then Nina can write b. The current word is bbb, and Emilija can't make a move, so Nina wins.

If Nina would first write a, Emilija could write b. The word would be ab, and Nina wouldn't be able to make a move, and she would lose.

Sample Input 2

2
acg
beh
2
bfj

Sample Output 2

Emilija

Sample Input 3

3
ja
sam
vlak
5
sto
zgazit
ce
te
mali

Sample Output 3

Nina