문제
성희는 영어 공부를 좋아하는 학생이다.
성희의 단어장은 다른 학생들과 차이가 있었는데,
그 단어장에는 알파벳 대문자(A, B, C, ..., Z)의 조합으로 이뤄진 동일한 길이의 N개의 단어들이 적혀있었다.
어느 날 성희는 영어 공부를 하다가 잠이 들었는데, 너무 침을 많이 흘린 나머지 이 단어들 중에서 몇 글자가 지워졌다.
이로 인해 공부하는데 문제가 생긴 성희는 상심하다가 그간 공부하던 기억을 되살려 다음 방법으로 단어장을 복구하고자 한다.
지워진 문자들을 임의의 알파벳으로 다시 써넣은 후,
모든 단어들을 한 행에 하나씩 열을 맞추어 나열했을 때
각 열이 비내림차순(non-decreasing order)으로 정렬되도록 단어들을 배열한다.
이러한 배열 방법 중 사전순으로 가장 작은 것을 출력하라. 지워진 문자는 물음표 '?' 표현된다.
두 배열 A, B에 대해 A가 B보다 사전순으로 작다는 뜻은
앞에서부터 따져 두 배열의 단어가 서로 다른 최초의 위치에서 A의 단어가 B의 단어보다 작다는 뜻이다.
단어장과 지워진 문자들이 주어졌을 때, 이를 복원하는 프로그램을 작성하라.
입력
입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 T 가 주어진다. (1 <= T <= 300) 각 테스트 케이스에 대해 입력의 첫 행에는 N 이 주어진다. (2 <= N <= 50) 다음 N 줄에 걸쳐, 알파벳 대문자와 물음표로 구성된 단어가 하나씩 주어진다. 단어의 길이는 50 이하이다.
출력
각 테스트 케이스에 대해 사전순으로 가장 작은 배열의 각 단어를 순서대로 한 행에 하나씩 출력한다. 만일 단어를 배치하는 방법이 존재하지 않을 경우 한 행에 "impossible"따옴표 제외)을 출력한다.
예제1
2
3
?ED?
TO??
????
5
A???J?
BC????
?DE???
??FG??
???HI?
AAAA
AEDA
TODA
impossible