SP3543 MATRICA - 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 $ _{i,j} $ = M $ _{j,i} $ for all pairs of i and j). For example, the following two matrices are symmetric: ``` AAB AAA ACC ABA BCC AAA ``` However, the following two are not: ``` ABCD AAB ABCD ACA 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.

The first line of input contains two integers N (1 ≤ N ≤ 30000) and K (1 ≤ K ≤ 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 ≤ P ≤ 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.

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).