기념(?)으로 문제 하나 풀어봐요

  똑똑한 과학자인 창식이는 최근 유전자에 대한 흥미가 생겨서 그에 대해 연구 중이다. 창식이는 여러 생물의 유전자의 공통점과 차이점에 대한 연구를 하고 있는데, 창식이는 유전자들을 잘 보다가 유전자들끼리 공통된 부분이 있다는 사실을 발견하였다.

  

  예를 들어서 AAATTCAGG 라는 유전자와 CATTCATGGG 라는 유전자는 둘 다 ATTCA 라는 공통 부분을 가지고 있다는 사실을 알 수 있다.

  공통 부분은 오로지 연속된 유전자만 가능하며, 길이가 2개 이상이어야 한다.

  이러한 사실에 흥미를 가지게 된 창식이는 3개의 유전자에서 공통된 부분을 찾는 연구를 하기로 하였으나, 갑작스러운 귀찮음의 습격으로 인해 연구를 하지 못하고있다. 유전자 연구를 하는 창식이를 도와주도록 하자.

입력:

3줄에 걸쳐서 입력이 들어온다.

각 줄은 대문자 ATCG로만 이루어진 공백없는 문자열이 들어온다.

문자열은 최대길이가 20만까지 가능하다.

출력:

3개의 유전자에서 가장 긴 공통 부분 유전자를 출력하도록 하자.

만약 가장 긴 공통 부분 유전자가 여러 개 있다면 그 중 아무거나 출력해도 좋다.

만약 공통 부분 유전자가 없다면, Impossible 을 출력하도록 하자.

창식이는 성격이 급하므로 프로그램에서 1초안에 답이 나오기를 바란다. 최대한 빠르게 짜보도록 하자.

예제1)

CATTTAAA

GATTTAG

CCCATTTGG

ATTT

예제2)

AAAAATTT

GGGGAGG

CCCCACC

Impossible

예제3)

ATATATA

ATATAT

TATATA

TATAT