MATRICA - Matrica

no tags 

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 (Mi,j = Mj,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 N2. 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.



Added by:Neal Wu
Date:2008-12-17
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Croatian Open 08/09 - Contest 3