Problem J
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_{ij} = M_{ji}$ for all pairs of $i$ and $j$).

The following figure shows two symmetric matrices and two which are not symmetric:

    AAB    AAA    ABCD    AAB
    ACC    ABA    ABCD    ACA
    BCC    AAA    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$.

Input

The first line of input contains two integers $N$ $(1 \leq N \leq 30\, 000)$ and $K$ $(1 \leq K \leq 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 \leq P \leq 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.

Output

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