유전자

인간 게놈 프로젝트에서는 염색체의 염기서열을 밝혀낸다. 그런데 한 염색체의 염기서열은 너무 길어서 현재 기술로는 한 번에 읽어낼 수 없다. 그래서 PCR로 염색체를 똑같이 여러 벌 복제한 다음, 효소를 가해 짧은 조각들로 잘라낸다. 각 조각은 충분히 짧으므로 그 내용을 읽어낼 수 있다. 읽어낸 조각들을 다시 이어 붙여 k벌의 동일한 염색체로 복원하면 원래 염색체의 전체 염기서열을 알아낼 수 있다.

염기는 A, G, T, C의 네 종류이며, 염기서열은 이 네 문자의 나열로 나타낸다. 각 조각은 읽은 방향 그대로 쓸 수도 있고, 좌우로 뒤집어(문자열을 역순으로 하여) 쓸 수도 있다.

예를 들어 어떤 염색체를 3벌 복제한 뒤 잘라 11개의 조각을 얻었고, 각 조각의 내용이 CGATGCCA, CAGGAAGCG, AGGTGCCC, CAGGA, AGGTGCCCGATGC, GGAAGCGATGGAGCTTT, ATGGAGCTTT, GATGC, CCGTGGA, AGCGATGG, TTTCGA라고 하자.

이 조각들을 아래와 같이 세 벌로 나누어 각 벌마다 조각들을 서로 겹치지 않게 차례로 이어 붙이면, 세 벌 모두 똑같은 염기서열 AGGTGCCCGATGCCAGGAAGCGATGGAGCTTT가 된다.

• AGGTGCCCGATGC + CAGGAAGCG + ATGGAGCTTT
• CCGTGGA를 뒤집은 AGGTGCC + CGATGCCA + GGAAGCGATGGAGCTTT
• AGGTGCCC + GATGC + CAGGA + AGCGATGG + TTTCGA를 뒤집은 AGCTTT

따라서 이때 복원되는 전체 염기서열은 AGGTGCCCGATGCCAGGAAGCGATGGAGCTTT이다.

복제한 벌 수 k와 읽어낸 조각들이 주어질 때 복원되는 전체 염기서열을 구하는 프로그램을 작성하시오. 각 조각은 정확히 한 벌에만 쓰이고, 주어진 모든 조각을 빠짐없이 사용한다. 입력은 항상 이러한 복원이 가능하도록 주어지며, 복원되는 염기서열은 읽는 방향(양 끝 중 어느 쪽에서 시작하는지)만 다를 뿐 유일하게 결정된다.

첫째 줄에 복제한 염색체의 벌 수 k가 주어진다 (2 ≤ k ≤ 20). 둘째 줄에 조각의 개수 n이 주어진다 (n ≤ 200). 이어지는 n개의 줄에 각 조각의 염기서열이 한 줄에 하나씩 주어진다. 각 조각의 길이는 5 이상 70 이하이며, 오직 A, G, T, C로만 이루어진다. 복원되는 전체 염기서열의 길이는 30 이상 700 이하이다.

복원되는 전체 염기서열을 한 줄에 출력한다. 복원된 염색체는 양 끝 중 어느 쪽에서 시작해 읽어도 같은 것으로 보므로, 복원한 염기서열과 그것을 뒤집은 서열 중 사전순으로 더 앞서는(작은) 쪽을 출력한다. 사전순 비교에서 문자의 대소는 A < C < G < T이다.