eolymp
bolt
Try our new interface for solving problems
Problems

Biodiversity

Biodiversity

Time limit 1 second
Memory limit 128 MiB

Alicia has a huge garden, which is the habitat of many animals that she really cares about. After listening to a podcast about biodiversity, she becomes very concerned about the balance between species in her garden. She wants to know if there is a species that could overtake the others. To do so, she decides to carry out a census of all the animals in the garden, writing down the species of each of them. Can you help her check if there are strictly more animals from one species than there are from all the other species together?

Input data

The first line contains the number of animals n~(1 \le n \le 2 \cdot 10^5);

Each of the next n lines contains an animal as a string of length at most 20, containing only ASCII alphanumeric characters.

Output data

Print a string that appears a number of times that is greater than the sum of the others, if there is any, or the string "NONE" otherwise.

Examples

Input example #1
3
frog
fish
frog
Output example #1
frog
Input example #2
4
cat
mouse
mouse
cat
Output example #2
NONE
Source 2019 ACM Southwestern Europe Regional Contest (SWERC), Paris, January 26 (2020), Problem B