A1378.[COCI-2008_2009-contest3]#4 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 (Mij = Mji for all pairs of i and j).
The following figure shows two symmetric matrices and one which is not symmetric:
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 rowmajor 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 N2 . 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).

In test cases worth 60% of points, N will be at most 300.
In test cases worth 80% of points, N will be at most 3000.