#1013 성희의 단어장

14  1 s   128 MB  

Description

성희는 영어 공부를 좋아하는 학생이다. 성희의 단어장은 다른 학생들과 차이가 있었는데, 그 단어장에는 알파벳 대문자(A,B,C,...,Z)의 조합으로 이뤄진 동일한 길이의 $N$개의 단어들이 적혀있었다. 어느날 성희는 영어 공부를 하다가 잠이 들었는데, 너무 침을 많이 흘린 나머지 이 단어들 중에서 몇 글자가 지워 졌다.이로인해 공부하는데 문제가 생긴 성희는 상심하다가 그간 공부하던 기억을 되살려 다음 방법으로 단어장을 복구 하고자 한다. 지워진 문자들을 임의의 알파벳으로 다시 써넣은 후, 모든 단어들을 한 행에 하나씩 열을 맞추어 나열했을 때 각 열이 비내림차순(non-decreasing order)으로 정렬되도록 단어들을 배열한다. 

이러한 배열 방법 중 사전순으로 가장 작은 것을 출력하라. 지워진 문자는 물음표 ?로 표현된다. 두 배열 $A$, $B$에 대해 $A$가 $B$보다 사전순으로 작다는 뜻은 앞에서부터 따져 두 배열의 단어가 서로 다른 최초의 위치에서 $A$의 단어가 $B$의 단어보다 작다는 뜻이다. 단어장과 지워진 문자들이 주어졌을 때, 이를 복원하는 프로그램을 작성하라.

Input

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 $T$ 가 주어진다. $(1 \leq T \leq 300)$ 각 테스트 케이스에 대해 입력의 첫 행에는 $N$ 이 주어진다. $(2  \leq N \leq 50)$ 다음 N 줄에 걸쳐, 알파벳 대문자와 물음표로 구성된 단어가 하나씩 주어진다. 단어의 길이는 $50$이하이다.

Output

각 테스트 케이스에 대해 사전순으로 가장 작은 배열의 각 단어를 순서대로 한 행에 하나씩 출력한다. 만일 단어를 배치하는 방법이 존재하지 않을 경우 한 행에 impossible을 출력한다.

Sample Input

Sample Output

2
3
?ED?
TO??
????
5
A???J?
BC????
?DE???
??FG??
???HI?
AAAA
AEDA
TODA
impossible

Source

2009 Ajou University Programming Contest