Trò chơi tiền tố

View as PDF

Time limit: 1.0s , Memory limit: 256M , Points: 100 (partial)

Nina và Emilija đang chơi trò chơi tiền tố. Mỗi người có một danh sách các từ yêu thích. Trò chơi bắt đầu với một tờ giấy trắng và Nina là người chơi đầu tiên. Lượt chơi được tiến hành luân phiên. Ở mỗi lượt chơi, người chơi lựa chọn và ghi lên giấy một ký tự chữ cái in thường bất kỳ, sao cho khi ghép các ký tự chữ cái đã ghi trên giấy theo thứ tự lượt chơi sẽ tạo thành tiền tố của một từ trong danh sách từ yêu thích của người chơi hiện tại.

Hãy xác định ai là người chiến thắng, giả sử rằng cả hai đều biết cách chơi tối ưu.

Input

  • Dòng đầu tiên chứa số nguyên n là số lượng từ trong danh sách yêu thích của Nina.
  • n dòng tiếp theo, mỗi dòng chứa một từ yêu thích của Nina.
  • Dòng tiếp theo chứa số nguyên m là số lượng từ trong danh sách yêu thích của Emilija.
  • m dòng tiếp theo, mỗi dòng chứa một từ yêu thích của Emilija.
  • Các từ đều bao gồm ký tự chữ cái in thường và tổng độ dài các từ của cả hai danh sách không vượt quá 2.10^5.

Output

  • In ra \text{Nina} hoặc \text{Emilija} là người chơi chiến thắng.

Samples

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

Scoring

  • Subtask 1 với 50\% số điểm: Tổng độ dài các từ không vượt quá 2000.
  • Subtask 2 với 50\% số điểm: Không còn ràng buộc gì thêm

Clarification

Ở ví dụ đầu tiên:

  • Nếu Nina lượt đầu tiên viết \text{b}, Emilija phải viết \text{b} ở lượt sau và Nina phải viết tiếp \text{b}. Từ trên giấy hiện tại là \text{bbb} và Emilija không thể viết tiếp, Nina thắng.
  • Nếu Nina lượt đầu tiên viết \text{a}, Emilija có thể lựa chọn viết \text{b} ở lượt sau. Khi đó từ trên giấy là \text{ab} và Nina không thể viết thêm, Emilija thắng.

Vì vậy, Nina nên lựa chọn viết \text{b} ở lượt đầu tiên để chiến thắng.


Comments