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_i,j = M_j,i for all pairs of i and j).

For example, the following two matrices are symmetric:

AAB          AAA
ACC          ABA
BCC          AAA

However, the following two are not:

ABCD          AAB
ABCD          ACA
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 ≤ 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.

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

Example

Input:
3 3
A 3
B 2
C 4
3
1 2 3

Output:
AAB
ACC
BCC

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

Output:
AC
BE
DE
ED

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

Output:
IMPOSSIBLE

Warning: large input/output data.

Note: The test data for this problem consist of the official test cases from the contest, as well some cases of my own.