대통령 선거

대선이 끝난 지 2주가 지났는데도 결과가 발표되지 않았다. 성제는 발표를 기다리는 대신 결과를 직접 알아보기로 했다.

성제는 나름의 방법으로 투표에 참여한 사람 전원의 후보 선호 순서를 한 명도 빠짐없이 조사했다. 유권자는 언제나 자신의 선호 순서에 따라 투표한다.

예를 들어 후보가 5명이고 어떤 유권자의 선호 순서가 [3, 2, 5, 1, 4]일 때 2번 후보와 4번 후보가 맞붙으면, 이 유권자는 2번 후보에게 투표한다. 선호 순서에서 2번이 4번보다 앞에 있기 때문이다.

투표 규칙은 다음과 같다.

• 후보는 $C$명, 유권자는 $V$명이다. 후보는 1부터 $C$까지의 정수로 구분하고, $V$는 항상 홀수이다.
• 투표는 최대 2회차까지 진행한다. 1회차에서는 모든 후보가 표를 받을 수 있고, 어떤 후보가 전체 표의 절반을 넘는 표를 얻으면 그 후보가 당선되어 투표가 끝난다.
• 1회차에서 절반을 넘긴 후보가 없으면 표를 가장 많이 받은 두 명만 2회차에 진출해 다시 투표한다. 2회차에서 절반을 넘는 표를 받은 후보가 최종 당선자다.
• 1회차 투표에서 2등 후보와 3등 후보의 득표수는 항상 다르다.
• 유권자의 선호 순서는 1회차와 2회차에서 같다.
• 기권표는 없다.

성제가 조사한 선호 순서를 보고 최종 당선자와 그 후보가 당선된 회차를 구하자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫 줄에 후보의 수 $C$와 유권자의 수 $V$가 주어진다. ($1 \le C, V \le 100$, $V$는 홀수)

이어지는 $V$개의 줄에 각 유권자의 선호 순서가 정수 $C$개로 주어진다. 앞에 나온 후보일수록 더 선호하는 후보이고, 마지막에 나온 후보가 가장 선호하지 않는 후보이다.

한 줄에 주어지는 정수 $C$개는 1부터 $C$까지의 모든 정수를 정확히 한 번씩 포함한다.

각 테스트 케이스마다 당선된 후보의 번호와 투표가 끝난 회차(1 또는 2)를 공백으로 구분해 한 줄에 출력한다.