DNA 진화
면접 대비시간 제한2초메모리 제한512 MB
각 위치에서 접두사와 겹치는 길이를 나타낸 배열이 주어질 때, 이를 만족하는 사전순으로 가장 작은 DNA 문자열을 찾습니다. 없으면 Impossible을 출력합니다.
문제
Fox Ciel에게 새 아기 여우 Jaro가 태어났다. Ciel은 오래전부터 유전학과 DNA 서열에 관심이 많았고, 이제 그 지식을 아들에게 적용해 보려 한다.
DNA는 뉴클레오타이드의 나열이다. 뉴클레오타이드는 A, C, G, T 네 종류가 있다. DNA는 부모에서 자식에게 전해지는데, 새로 태어난 여우는 아버지보다 뉴클레오타이드가 하나 더 많다. 새 뉴클레오타이드는 서열의 맨 앞에 붙는다. 예를 들어 Ciel의 DNA가 CACAA이면 아들 Jaro의 DNA는 ACACAA이다. Jaro가 새로 얻은 A가 맨 앞에 있고, 나머지는 Ciel에게서 물려받은 것이다.
Ciel은 조상들의 DNA를 모두 적고, 각 조상의 DNA와 Jaro의 DNA 사이 유사도 계수를 계산했다. 유사도 계수는 두 DNA가 공통 접두사로 가지는 문자의 최대 개수이다. Ciel은 결과를 아래 표의 노트에 기록했다. formal한 정의는 힌트에 있다.
토끼 Hanako가 실수로 노트에서 Jaro의 DNA 서열을 지워 버렸다. Ciel이 이 사실을 알아채면 Hanako를 공격해서 잡아먹을 것이다. Hanako가 DNA 서열을 최대한 빨리 복원하도록 도와라.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다(1 ≤ T ≤ 100). 각 테스트 케이스는 공백으로 구분된 정수들이 한 줄에 주어진다. 첫 번째 정수는 DNA 서열의 길이 N이고, 이어서 N개의 정수 a_i가 주어진다. a_i는 위치 i(0 ≤ i < N)의 유사도 계수이다.
제약 조건: 1 ≤ N ≤ 10^5, 0 ≤ a_i ≤ 10^5.
출력
각 테스트 케이스마다 DNA 서열 S를 한 줄에 출력한다. 가능한 서열이 여러 개이면 사전순으로 가장 앞서는 서열을 출력한다. 가능한 서열이 없으면 Impossible을 출력한다.
힌트
S의 길이를 n이라 하자. 노트는 배열 A이며, A_i는 S_i에서 시작하는 부분 문자열 중 S의 접두사이기도 한 가장 긴 것의 길이이다. 다시 말해 모든 0 ≤ j < k에 대해 S_j = S_{i+j}가 성립하는 최대의 k이다.