Problem Description

Nina and Emilija are playing a game on a piece of paper. Initially, the paper is blank. In each turn, a player appends a letter to the end of a word on the paper. They then take turns alternately. Nina starts first.

The players must follow this rule when choosing letters: after each addition, the word must be a prefix of a word from the player's favorite song. If a player cannot proceed in their turn, they lose.

Determine the winner if both players are playing optimally.

Input Format

The first line contains a positive integer \( n \), representing the number of words in Nina's favorite song.

The next \( n \) lines each contain a word from Nina's favorite song.

The following line contains a positive integer \( m \), representing the number of words in Emilija's favorite song.

The next \( m \) lines each contain a word from Emilija's favorite song.

All input words consist of lowercase letters, and the total length of all words does not exceed \( 200000 \).

Output Format

Output the winning player, either Nina or Emilija.

Sample Input and Output

Sample Input #1

2
aaa
bbb
3
aab
aba
bbb

Sample Output #1

Nina

Sample Input #2

2
acg
beh
2
adi
bfj

Sample Output #2

Emilija

Sample Input #3

3
ja
sam
vlak
5
sto
zgazit
ce
te
mali

Sample Output #3

Nina

Notes/Hints

Sample 1 Explanation

If Nina writes the letter b first, Emilija must then write b, and Nina will continue with b. The current word becomes bbb, and Emilija cannot proceed, so Nina wins.

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

Data Size and Constraints

For \( 40 \) points, the total length of all words does not exceed \( 2000 \).

For \( 100\% \) of the data, the total length of all words does not exceed \( 200000 \).

Note

This problem's score is set according to the original COCI contest, with a maximum of \( 70 \) points.

The problem is translated from COCI2020-2021 CONTEST #3 T2 Vlak.

见题面 Input 部分

见题面 Output 部分