Suffix Array Re-construction

It has been a long day at your new job. You spent all day optimizing the most important suffix-array data structures your new employer works with. Just as you were about to shut down your workstation, a test run reveals that large portions of the important data have been corrupted -- and, sadly, the backup servers crashed only yesterday.

On inspection, the data could hardly be worse. Many suffixes are missing, and the ones that remain may be broken: in some, letters have been replaced by random letters; in some, a contiguous block of characters was replaced by a single placeholder character *; and some suffixes are simply inconsistent with one another. Your only hope now is to reconstruct the underlying base strings, if it is possible at all.

The data is given as a list of suffixes, each with its start position, together with the length of each desired string. Reconstruct each base string if you can.

How reconstruction works. Each suffix starts at a position $p$ and describes the characters of the string from position $p$ through the last position $l$. Within a suffix, the character * is a placeholder standing for a contiguous, non-empty block of lost characters: the characters written before the * correspond to positions $p, p+1, \dots$ counting from the start of the suffix, and the characters written after the * correspond to the positions ending at $l$, counting back from the end of the string. A suffix without a * lists every character from position $p$ to $l$. Each suffix contains at most one *.

For every position of the string, gather the characters claimed for it by all the suffixes. Reconstruction is possible only if every position is claimed by at least one character and all claims for that position agree -- that is, the set of possible characters for that position contains exactly one character.

The first line contains the number of test cases $t$ ($0 < t \le 100$). Each test case is given as follows. The first line contains two integers $l$ and $s$ ($1 \le l \le 10000$; $1 \le s \le 10000$): the length of the desired string and the number of (partially broken) suffixes. Each of the next $s$ lines contains a start position $p$ ($1 \le p \le l$) and the suffix string. Each suffix consists only of the characters a–z, A–Z, ., and * (the . has no special meaning) and contains at most one *. The total number of characters over all suffixes does not exceed $250000$.

For each test case, if the string can be reconstructed, print it on a single line; otherwise print IMPOSSIBLE on a single line.