문제
'a', 'g', 't', 'c'로 이뤄진 문자열 - 염기서열 - 이 주어졌을 때 이를 앞, 뒤 어느 쪽에서 읽어도 동일한 경우 이를 pDNA라고 한다. 예를 들어 'actca'는 pDNA이고, 'agtc'는 pDNA가 아니다.
꿈에 그리던 대학에 입학한 동훈이는 보이지 않는 손에 의해 bioinformatics를 연구하는 연구실의 인턴이 되어있었다. 최근 동훈이가 맡은 과제는 위에 설명된 pDNA를 찾는 것이다. 며칠간의 밤샘 작업을 하여 여러 개의 pDNA를 찾은 동훈이는 자신이 한 일에 보람을 느끼며 연구실에서 퇴근하였다.
연구실의 모든 사람들이 퇴근하여 아무도 없는 새벽에 만취 상태의 철기가 들어와서 동훈이의 자리를 자신의 자리로 착각하고 그곳에 앉아서 컴퓨터를 쓰게 되었다.
평소에 바탕화면을 워낙 깨끗하게 쓰기로 유명한 철기는, 동훈이의 컴퓨터를 켰을 때 너무나 많은 바탕화면의 아이콘을 보고, '악성코드가 생겼나' 라는 생각을 하며 바탕화면에 있는 모든 것을 지워버렸다. 그런데 하필이면 동훈이가 찾은 pDNA의 데이터는 바탕화면에 저장이 되어있었다!
간만에 숙면을 하고 말끔해진 피부로 연구실에 나온 동훈이는 아침에 컴퓨터를 키고나서 데이터가지워진 사실을 알고 경악하였다! 그리하여 부랴부랴 last data라는 복원 프로그램을 사용하여 복원을 시도하였으나, 발견한 pDNA들이 조각이 나고 순서가 뒤죽박죽 바뀐 상태로 복원이 되었다.
당황한 동훈이는 절친인 당신에게 도움을 청했다. 동훈이를 도와서 pDNA 데이터를 복원하는 프로그램을 작성해야한다!
입력
입력의 처음에는 조각의 개수 P(P <= 10)가 주어지며, 그 다음 부터는 P개의 조각이 주어진다.
P와 조각의 사이와, 조각과 조각의 사이는 정확히 스페이스로 띄어져 있다.
조각은 알파벳 소문자 'a', 'g', 't', 'c'로 주어지며, 모든 조각의 길이의 합은 최대 100자 이하다.
출력
입력에 대해 복원된 pDNA의 결과를 출력한다.
답이 존재하지 않는 경우는 없으며, 만약에 가능한 경우가 여럿 있을 경우 사전순으로 가장 앞에 나오는 것(lexicographically first)을 출력한다.
예제
4 ac tgt ac caca
acactgtcaca
로그인해야 코드를 작성할 수 있어요.