깃발 퀴즈

은하계의 저예산 스트리밍 프로그램 깃발 퀴즈!''에서 참가자들은 제국 $X$의 깃발들에 공통으로 나타나는 색, 기호, 모양은 무엇인가?''와 같은 질문에 답해야 한다. 여기서 제국이란 단순히 같은 행성에 존재하거나, Supreme Map Maker의 상상에 따라 그 밖의 방식으로 서로 관련된 개체들의 어떤 부분집합이다. 예를 들어 Supreme Map Maker가 정한 체계에 따르면, ``Empire Earth Meridian 0''는 모두 지구의 본초 자오선이 가로지르는 국가들이다. 이는 각 행성에서 현지에 사용되는 체계와 반드시 같지는 않다. 예를 들어 이 체계에서는 본초 자오선이 Stockholm을 지난다. 지리, 정치 또는 문화에 관한 지식은 실제로 이 도전에서 승리하는 데 방해가 될 수도 있다!

하지만 때로는(사실 대부분의 경우에는) 선택지만 살펴봐도 퀴즈 질문의 답을 알아낼 수 있다. 저예산 프로그램이기 때문에, 낮은 임금을 받는 퀴즈 문제 작성자들은 각 질문의 선택지를 만드는 데 드는 노력을 최소화하려 한다. 이들은 정답에 적은 수의 변경을 가하여 각 선택지를 만들며, 하나의 변경은 정답의 한 부분을 다른 것으로 교체하는 것이다. 예를 들어 초록색, 파란색, 줄무늬''를 초록색, 노란색, 줄무늬''로 바꾸는 데에는 단 하나의 변경이 있지만, 같은 답을 생명, 우주, 줄무늬''로 바꾸는 데에는 두 번의 변경이 있다. 문제 작성자들은 부분들의 순서를 절대 바꾸지 않으므로 순서가 중요하다. 다시 말해, 초록색, 파란색, 줄무늬''를 ``줄무늬, 파란색, 초록색''으로 바꾸는 경우, 엄밀히 말해 둘이 같은 답이더라도 두 번의 변경이 있다.

여러분의 과제는 이러한 방식으로 만들어진 질문에서 가장 가능성 높은 답을 자동으로 찾는 프로그램을 작성하는 것이다. 한 선택지의 비일치도를 그 선택지를 다른 선택지 중 어느 것으로든 바꾸는 데 필요한 변경 횟수의 최댓값으로 정의한다. 그러면 비일치도가 가장 작은 선택지(들)을 찾는다.

과제

질문 하나와 그에 대한 가능한 답들의 집합이 주어질 때, 다른 어떤 답으로든 가장 쉽게 바꿀 수 있는 답을 찾는다.

첫째 줄에 답해야 할 질문이 주어진다. 다음 줄에는 답안 선택지의 수를 나타내는 양의 정수 하나 $1 \leq N \leq 100$이 주어진다. 다음 $N$개의 줄에는 각 줄마다 선택지 하나가 주어진다. 선택지는 쉼표와 공백으로 구분된 부분들의 목록이다. 모든 답은 같은 수의 부분으로 이루어지며, 그 수는 최대 100이다. 모든 부분은 문자 a-z와 A-Z, 숫자 0-9, 공백으로 이루어진 문자열이다. 부분의 최대 길이는 50자이다.

다른 어떤 답으로든 바꾸는 데 필요한 변경 횟수의 최댓값이 가장 작은 선택지를 출력한다. 비일치도가 가장 작은 선택지가 여러 개라면 입력에 주어진 것과 같은 순서로 모두 출력한다.