Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
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. In order to do so, she decides to carry out a census of all animals in the garden, writing down the species of each of them. Can you help her checking if there is strictly more animals from one species than the animals from all other species together?
Input
The input consists of the following lines:
on the first line: an integer $$$N$$$;
on each of the next $$$N$$$ lines: the species of an animal as a string of length at most 20, containing only ASCII alphanumeric characters.
Limits
$$$1 \le N \le 2 \times 10^5$$$.
Output
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.