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

3 3
A 3
B 2
C 4
3
1 2 3

AAB
ACC
BCC

4 4
A 4
B 4
C 4
D 4
4
1 2 3 4

AABB
AACC
BCDD
BCDD

4 5
E 4
A 3
B 3
C 3
D 3
2
2 4

AC
BE
DE
ED

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

IMPOSSIBLE