# Problem J

Matrica

A matrix is a rectangular table of letters. A square matrix is a matrix with an equal number of rows and columns. A square matrix $M$ is called symmetric if its letters are symmetric with respect to the main diagonal ($M_{ij} = M_{ji}$ for all pairs of $i$ and $j$).

The following figure shows two symmetric matrices and two which are not symmetric:

AAB AAA ABCD AAB ACC ABA ABCD ACA BCC AAA ABCD DAA ABCD

Given a collection of available letters, you are to output a
subset of columns in the lexicographically smallest symmetric
matrix which can be composed using all the letters. If no such
matrix exists, output “`IMPOSSIBLE`”.

To determine if matrix $A$ is lexicographically smaller than matrix $B$, consider their elements in row-major order (as if you concatenated all rows to form a long string). If the first element in which the matrices differ is smaller in $A$, then $A$ is lexicographically smaller than $B$.

## Input

The first line of input contains two integers $N$ $(1 \leq N \leq 30\, 000)$ and $K$ $(1 \leq K \leq 26)$. $N$ is the dimension of the matrix, while $K$ is the number of distinct letters that will appear.

Each of the following $K$ lines contains an uppercase letter
and a positive integer, separated by a space. The integer
denotes how many corresponding letters are to be used. For
example, if a line says “`A 3`”, then
the letter $A$ must appear
three times in the output matrix.

The total number of letters will be exactly $N^2$. No letter will appear more than once in the input. The next line contains an integer $P$ $(1 \leq P \leq 50)$, the number of columns that must be output. The last line contains $P$ integers, the indices of columns that must be output. The indices will be between 1 and $N$ inclusive, given in increasing order and without duplicates.

## Output

If it is possible to compose a symmetric matrix from the
given collection of letters, output the required columns on
$N$ lines, each containing
$P$ character, without
spaces. Otherwise, output “`IMPOSSIBLE`” (quotes for clarity).

Sample Input 1 | Sample Output 1 |
---|---|

3 3 A 3 B 2 C 4 3 1 2 3 |
AAB ACC BCC |

Sample Input 2 | Sample Output 2 |
---|---|

4 4 A 4 B 4 C 4 D 4 4 1 2 3 4 |
AABB AACC BCDD BCDD |

Sample Input 3 | Sample Output 3 |
---|---|

4 5 E 4 A 3 B 3 C 3 D 3 2 2 4 |
AC BE DE ED |

Sample Input 4 | Sample Output 4 |
---|---|

4 6 F 1 E 3 A 3 B 3 C 3 D 3 4 1 2 3 4 |
IMPOSSIBLE |