Новый президент
Наконец, пришло время проголосовать за нового президента, чему Вы очень рады. Вы знаете, что окончательные результаты могут быть объявлены через несколько недель, в то время как Вы сами не желаете долго ждать результатов.
Каким-то образом Вам удалось получить список предпочтений для каждого избирателя (нас не интересует как Вы получили эту часть информации!). Каждый избиратель отсортировал всех кандидатов, начиная с наиболее предпочтительного и заканчивая наименее предпочитаемым. При голосовании избиратель голосует за кандидата, который стоит на первом месте в его списке предпочтений. Например, если имеется 5 кандидатов (пронумерованных от 1 до 5), список предпочтений для одного избирателя [3, 2, 5, 1, 4], текущими конкурирующими кандидатами при голосовании являются 2 и 4, то избиратель проголосует за кандидата номер 2.
Следующие правила описывают выборный процесс:
Всего имеется c кандидатов (пронумерованных от 1 до c), и v избирателей (v всегда нечетно).
Выборы могут проходить не более чем в два раунда. Все кандидаты принимают участие в первом раунде. Если кандидат получает более 50% голосов, он побеждает, иначе имеет место второй раунд, в котором участвуют только 2 кандидата с наилучшими результатами. Кандидат, получивший большее количество голосов нежели его оппонент, становится новым президентом.
Вы можете с уверенностью считать, что имеющиеся предпочтения никогда не приведут к ситуации, в которой второй и третий кандидаты в первом туре получат одинаковое количество голосов.
Предпочтения избирателей одинаковы в обоих раундах, каждый избиратель голосует в каждом раунде только один раз за кандидата в соответствии со своими предпочтениями.
По спискам предпочтений Вам следует написать программу, которая выяснит, какой кандидат победит и в каком раунде.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Первая строка каждого теста содержит два целых числа c и v (1 ≤ c, v ≤ 100) - количество кандидатов и избирателей. Каждая из следующих v строк содержит по c целых чисел - предпочтения одного избирателя (первое число указывает на наиболее предпочтительного кандидата, последнее - на наименее предпочтительного). Каждое число от 1 до c встречается в каждой строке только один раз.
Выходные данные
Для каждого теста вывести два числа в отдельной строке. Первое число - ID победившего кандидата (число от 1 до c), второе число - 1 или 2 в зависимости от того, победил ли он в первом или во втором раунде.