Новий президент
Нарешті настав час обрати нового президента, і ви з нетерпінням чекаєте на результати. Ви знаєте, що остаточні результати можуть бути оголошені лише через кілька тижнів, але вам не хочеться так довго чекати.
Якимось чином ви отримали список уподобань кожного виборця (ми не будемо питати, як ви це зробили!). Кожен виборець впорядкував усіх кандидатів від найбільш до найменш бажаного. Під час голосування виборець віддає свій голос кандидату, який стоїть на першому місці в його списку уподобань. Наприклад, якщо є 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 в залежності від того, переміг він у першому чи у другому раунді.