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 is called symmetric if its letters are symmetric with respect to the main diagonal ( for all pairs of and ).
The following figure shows two symmetric matrices and one which is not symmetric:
AAB AAA
ACC ABA
BCC AAA
Two symmetric matrices.
ABCD AAB
ABCD ACA
ABCD DAA
ABCD
Two matrices that are 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 is lexicographically smaller than matrix , 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 , then is lexicographically smaller than .
Input Specification
The first line of input contains two integers and . is the dimension of the matrix, while is the number of distinct letters that will appear.
Each of the following 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 must appear three times in the output matrix.
The total number of letters will be exactly . No letter will appear more than once in the input. The next line contains an integer , the number of columns that must be output. The last line contains integers, the indices of columns that must be output. The indices will be between and inclusive, given in increasing order and without duplicates.
Output Specification
If it is possible to compose a symmetric matrix from the given collection of letters, output the required
columns on lines, each containing character, without spaces. Otherwise, output IMPOSSIBLE
.
Scoring
In test cases worth of points, will be at most . In test cases worth of points, will be at most .
Sample Input 1
3 3
A 3
B 2
C 4
3
1 2 3
Sample Output 1
AAB
ACC
BCC
Sample Input 2
4 4
A 4
B 4
C 4
D 4
4
1 2 3 4
Sample Output 2
AABB
AACC
BCDD
BCDD
Sample Input 3
4 5
E 4
A 3
B 3
C 3
D 3
2
2 4
Sample Output 3
AC
BE
DE
ED
Sample Input 4
4 6
F 1
E 3
A 3
B 3
C 3
D 3
4
1 2 3 4
Sample Output 4
IMPOSSIBLE
Comments