35512번 - Good Bye, 소가 길을 건너간 이유!

https://www.acmicpc.net/workbook/view/6537

농부 존(Farmer John)의 소들은 BOJ의 마지막을 기념하기 위한 특별 퍼레이드를 준비했다. 퍼레이드에 참가한 소 $L$마리는 일렬로 줄을 서서 길을 건너는 퍼포먼스를 선보였다. 소가 길을 건너간 이유는 바로 BOJ를 위한 퍼레이드였던 것이다!

소들은 출신지에 따라 몸의 무늬가 다르다. 맨 앞에서 무리를 이끄는 우두머리 소의 무늬는 알파벳 대문자 A-Z로 표현할 수 있다. 나머지 $L-1$마리 일반 소들의 무늬는 알파벳 소문자 a-z로 표현할 수 있다. 여러 소가 같은 무늬를 가질 수도 있다.

존은 소들이 길을 건너는 모습을 총 $N$장의 사진에 담았다. 소들은 항상 정해진 순서대로 줄을 서서 길을 건너지만, 왼쪽을 향해 길을 건널 때도 있고 오른쪽을 향해 길을 건널 때도 있기 때문에 사진에 찍힌 소들의 좌우 순서는 뒤집힐 수 있다.

그런데 존이 사진을 정리하던 도중 말썽꾸러기 베시(Bessie)가 잉크 통을 엎지르는 바람에 사진의 일부가 가려지고 말았다. 훼손된 사진은 다음과 같은 길이 $L$의 문자열로 나타낼 수 있다.

• $i$번째 문자는 해당 사진을 찍을 때 왼쪽에서 $i$번째 위치에 있던 소의 정보이다.
• A-Z와 a-z는 사진에 보이는 소의 무늬를 의미한다.
• .은 해당 위치의 소가 잉크에 가려져 보이지 않음을 의미한다.
• 사진의 소들은 왼쪽을 향해 길을 건넜을 수도 있고, 오른쪽을 향해 길을 건넜을 수도 있다. 즉, 양쪽 끝에 있는 두 소가 모두 잉크로 가려져서 어느 소가 우두머리인지 모른다면 소들의 방향을 알 수 없다.

농부 존은 $N$장의 사진에 남아 있는 정보를 이용해, 아래 형식으로 $L$마리의 소가 줄을 선 원래 순서를 복원하려고 한다.

• $i$번째 문자는 앞에서 $i$번째 소의 정보를 의미하며, 첫 번째 소는 우두머리 소이다.
• 무늬를 확실하게 알 수 있는 소는 A-Z 또는 a-z로 그 무늬를 나타낸다.
• 무늬를 확실하게 알 수 없는 소는 .으로 나타낸다.

$L$마리의 소가 줄을 선 순서를 복원하는 프로그램을 작성하시오.

첫째 줄에 정수 $L,N$이 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 각 사진의 정보를 나타내는 길이 $L$의 문자열이 주어진다.

문자열은 A-Z, a-z, .으로만 이루어져 있다. A-Z는 문자열의 양 끝에만 나타날 수 있다. 또한, 문자열의 양 끝 문자가 모두 A-Z이거나 모두 a-z인 경우는 없다. 다시 말해, 사진 한 장에 우두머리 소가 두 마리 찍히거나, 양 끝에 찍힌 소가 모두 일반 소인 경우는 없다.

첫째 줄에 소가 줄을 선 순서를 나타내는 길이 $L$의 문자열을 출력한다.

만약 $N$장의 사진에 모두 부합하는 소들의 순서가 존재하지 않는다면 대신 IMPOSSIBLE을 출력한다.

• $2\le L\le 100$
• $1\le N\le 30\,000$
• 문자열은 A-Z, a-z, .으로만 이루어져 있다.
• A-Z는 문자열의 양 끝에만 나타날 수 있다.
• 문자열의 양 끝 문자가 모두 A-Z이거나 모두 a-z인 경우는 없다.