COCI 2020/2021 - Contest 3 - Vlak

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 3
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nina và Emilija đang chơi một trò chơi trên một tờ giấy. Trước khi bắt đầu, tờ giấy vẫn chưa được viết gì. Ở mỗi lượt, người chơi phải viết một chữ cái vào cuối từ hiện có trên tờ giấy. Họ thay phiên nhau chơi, và Nina bắt đầu trước.

Người chơi phải chọn chữ cái sao cho từ hiện có trên tờ giấy sau khi thêm chữ cái đó vào sẽ trở thành tiền tố của của ít nhất một từ trong bài hát yêu thích của người chơi đó. Người chơi sẽ thua nếu không tìm được bất kì chữ cái nào phù hợp.

Nếu cả hai người đều chơi một cách tối ưu, hãy xác định xem ai là người thắng cuộc.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~, số từ trong bài hát yêu thích của Nina. Mỗi dòng trong số ~n~ dòng tiếp theo chứa một từ trong bài hát yêu thích của Nina.

Dòng tiếp theo chứa một số nguyên dương ~m~, số từ trong bài hát yêu thích của Emilija. Mỗi dòng trong số ~m~ dòng tiếp theo chứa một từ trong bài hát yêu thích của Emilija.

Các từ trong bài hát chỉ chứa các chữ cái viết thường và tổng độ dài của tất cả các từ không vượt quá ~200\:000~.

Output

Một dòng duy nhất ghi ~\texttt{Nina}~ hoặc ~\texttt{Emilija}~, tên của người thắng cuộc.

Subtask

  • ~16~ test có tổng độ dài của tất cả các từ không quá ~2000~.
  • ~12~ test còn lại không có ràng buộc gì thêm.

Sample 1

Input
2
aaa
bbb
3
aab
aba
bbb
Output
Nina
Giải thích

Nếu Nina đầu tiên viết ~\texttt{b}~, Emilija phải viết ~\texttt{b}~, và sau đó Nina có thể viết ~\texttt{b}~. Từ hiện có trên tờ giấy là ~\texttt{bbb}~ nên Emilija không thể ghi thêm bất kì chữ cái nào. Do đó, Nina thắng.

Nếu Nina đầu tiên viết ~\texttt{a}~, Emilija có thể viết ~\texttt{b}~. Từ hiện có trên tờ giấy là ~\texttt{ab}~ nên Nina không thể ghi thêm bất kì chữ cái nào. Do đó, Nina thua.

Sample 2

Input
2
acg
beh
2
adi
bfj
Output
Emilija

Sample 3

Input
3
ja
sam
vlak
5
sto
zgazit
ce
te
mali
Output
Nina

Comments

Please read the guidelines before commenting.


There are no comments at the moment.