기업 아이덴티티

ACM은 여러 서비스와 함께, 기업이 회사 로고뿐만 아니라 상표(trademark)와 같은 다른 표식까지 아우르는 "기업 아이덴티티(corporate identity)"를 분명하게 드러내도록 돕는다. 그런 기업 가운데 하나인 Internet Building Masters(IBM)는 최근 새로운 아이덴티티를 만드는 일을 ACM에 의뢰했다. 다만 IBM의 고객들은 기존 로고와 상표에 이미 익숙하므로, IBM은 이들을 완전히 새로 바꾸고 싶어 하지 않는다. 그래서 ACM은 새 상표를 만드는 대신 기존 상표를 조금만 손질하기로 했다.

여러 차례 논의 끝에, 기존의 모든 상표를 모아서 그 모두에 공통으로 들어 있는 가장 긴 글자열(연속된 부분 문자열)을 찾기로 결정했다. 이 문자열을 시각적으로 강조하여 새 로고를 구성하고, 새 아이덴티티를 보여 주면서도 기존 상표를 계속 사용할 수 있게 하려는 것이다.

당신이 할 일은 그런 문자열을 찾는 것이다.

입력은 여러 개의 작업(task)으로 이루어진다. 각 작업은 상표의 개수를 나타내는 양의 정수 $N$ ($2 \le N \le 4000$)이 적힌 한 줄로 시작한다. 그 뒤에 $N$개의 줄이 이어지며, 각 줄에는 상표가 하나씩 적혀 있다. 상표는 모두 소문자 알파벳으로만 이루어지고, 각 상표의 길이는 최소 $1$, 최대 $200$이다.

어떤 작업의 마지막 상표 다음에는 곧바로 다음 작업이 이어진다. 마지막 작업 뒤에는 $0$ 하나만 적힌 줄이 온다.

각 작업마다, 모든 상표에 연속된 부분 문자열(substring)로 포함되는 가장 긴 문자열을 한 줄에 출력한다. 길이가 같은 문자열이 여러 개라면 사전순으로 가장 앞서는 것을 출력한다. 그러한 비어 있지 않은 문자열이 존재하지 않으면, 대신 "IDENTITY LOST"를 출력한다.