Symmetric Matrix

A matrix is a rectangular table filled with characters. A square matrix has the same number of rows and columns. A square matrix M is symmetric when M_{i,j} = M_{j,i} for every pair i, j.

The following two matrices are symmetric.

AAB        AAA
ACC        ABA
BCC        AAA

The following two matrices are not symmetric.

ABCD        AAB
ABCD        ACA
ABCD        DAA
ABCD

You are given the available characters and how many times each one may be used. Among all symmetric matrices that can be made by using every character exactly once, choose the lexicographically smallest matrix. Print the submatrix that remains after keeping only the specified columns of that matrix.

A subset of columns of a matrix is the matrix obtained by deleting all columns except the chosen ones. Consider this matrix:

AAB
ACC
BCC

Keeping columns 1 and 3 gives the following matrix.

AB
AC
BC

To compare two matrices lexicographically, read each matrix row by row from top to bottom and left to right, concatenate the characters into one string, and compare those strings.

The first line contains two integers N and K. N is the size of the matrix, and K is the number of distinct available characters. (1 <= N <= 30000, 1 <= K <= 26)

Each of the next K lines contains an available character and its count, separated by a space. Every character is an uppercase English letter. For example, A 3 means that A may be used 3 times.

The total number of available characters is exactly N^2.

The next line contains P, the size of the column subset. (1 <= P <= 50)

The last line contains the P column numbers to keep. Each number is between 1 and N, the numbers are strictly increasing, and there are no duplicates.

If a symmetric matrix can be made from the given characters, print the specified column subset of the lexicographically smallest such symmetric matrix.

If no symmetric matrix can be made, print IMPOSSIBLE.