접미사 배열 복원

새 직장에서의 긴 하루였다. 당신은 하루 종일, 새 고용주가 다루는 가장 중요한 접미사 배열(suffix array) 자료구조를 최적화했다. 워크스테이션을 막 끄려던 순간, 테스트 실행 결과 중요한 데이터의 상당 부분이 손상되었음이 드러났다. 게다가 백업 서버는 어제 고장 났다.

데이터를 살펴보니 상황은 매우 나빴다. 많은 접미사가 사라졌고, 남아 있는 것들도 손상되었을 수 있다. 어떤 접미사에서는 일부 글자가 임의의 글자로 바뀌었고, 어떤 접미사에서는 연속한 문자 덩어리가 하나의 자리표시 문자 *로 대체되었으며, 서로 모순되는 접미사들도 있다. 이제 남은 희망은 원래의 기반 문자열을 복원하는 것뿐이다.

데이터는 각 접미사와 그 시작 위치의 목록으로 주어지며, 복원해야 할 각 문자열의 길이도 함께 주어진다. 가능하다면 각 기반 문자열을 복원하여라.

복원 규칙. 각 접미사는 위치 $p$에서 시작하여, 문자열의 위치 $p$부터 마지막 위치 $l$까지의 문자들을 나타낸다. 접미사 안에서 문자 *는 사라진, 연속하며 비어 있지 않은 문자 덩어리를 대신하는 자리표시자이다. * 앞에 적힌 문자들은 접미사의 시작에서부터 세어 위치 $p, p+1, \dots$에 대응하고, * 뒤에 적힌 문자들은 문자열의 끝 $l$에서부터 거꾸로 세어 그 위치들에 대응한다. *가 없는 접미사는 위치 $p$부터 $l$까지의 모든 문자를 나열한다. 각 접미사에는 *가 최대 하나 있다.

문자열의 각 위치에 대해, 모든 접미사가 그 위치에 대해 주장하는 문자들을 모은다. 모든 위치가 적어도 하나의 문자로 주장되고 각 위치에 대한 모든 주장이 일치할 때에만, 즉 그 위치에서 가능한 문자의 집합이 정확히 하나의 문자만을 포함할 때에만 복원이 가능하다.

첫째 줄에는 테스트 케이스의 수 $t$ ($0 < t \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다. 첫째 줄에는 두 정수 $l$과 $s$ ($1 \le l \le 10000$; $1 \le s \le 10000$)가 주어지며, 각각 복원할 문자열의 길이와 (일부 손상된) 접미사의 개수이다. 이어지는 $s$개의 줄에는 각각 접미사의 시작 위치 $p$ ($1 \le p \le l$)와 접미사 문자열이 주어진다. 각 접미사는 a–z, A–Z, ., * 문자로만 이루어지며(.은 특별한 의미가 없다), *를 최대 하나 포함한다. 모든 접미사에 주어진 문자 수의 총합은 $250000$을 넘지 않는다.

각 테스트 케이스마다, 문자열을 복원할 수 있으면 그 문자열을 한 줄에 출력하고, 그렇지 않으면 IMPOSSIBLE을 한 줄에 출력한다.