시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 17 | 14 | 13 | 81.250% |
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.
The first line contains a positive integer n, the number of words in Nina’s favourite song. Each of the following n lines contains a word from Nina’s favourite song.
The following line contains a positive integer m, the number of words in Emilija’s favourite song. Each of the following m 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 200 000.
Output Nina
or Emilija
, the name of the winner.
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
Clarification of the first example:
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.