В Москве проходит крупная международная конференция, на которую приехали n ученых из разных стран. Каждый из ученых говорит ровно на одном языке. Для удобства пронумеруем все языки мира целыми числами от 1 до 109.
Вечером после конференции все n учёных решили сходить в кино. В кинотеатре, в который они пришли, показывают m фильмов. Каждый из фильмов характеризуется двумя различными числами — номером языка озвучивания bi, а также номером языка субтитров ci. Учёный, пришедший на фильм, будет очень доволен, если знает язык озвучивания фильма, будет почти доволен, если знает язык субтитров, и будет совсем недоволен, если не знает ни того, ни другого (обратите внимание, что языки озвучивания и субтитров у каждого фильма всегда различны).
Учёные решили все вместе пойти на один и тот же фильм. Вам предстоит помочь им выбрать такой фильм, при просмотре которого будет максимально возможное количество очень довольных учёных. Если таких фильмов несколько, нужно выбрать из них такой, при просмотре которого будет максимально возможное количество почти довольных учёных.
Выходные данные
Выведите единственное целое число — номер фильма, на который должны пойти учёные. При просмотре этого фильма должно быть максимально возможное количество очень довольных учёных. Если таких фильмов несколько, нужно выбрать из них такой, при просмотре которого будет максимально возможное количество почти довольных учёных.
Если ответов несколько, разрешается вывести любой из них.
Примечание
В первом тестовом примере учёные должны пойти на фильм номер 2, так как в этом случае 1-й и 3-й учёные будут очень довольны, а 2-й учёный будет почти доволен.
Во втором тестовом примере учёные могут пойти либо на фильм номер 1, либо на фильм номер 3. При просмотре любого из этих фильмов ровно два учёных будут очень довольны, а все остальные будут совсем недовольны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3 2
2
3 2
2 3
|
2
|
|
2
|
6
6 3 1 1 3 7
5
1 2 3 4 5
2 3 4 5 1
|
1
|