프로그램 명: coci_matrica
제한시간: 1 초

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

입출력 예

input 

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

output 

AAB 
ACC 
BCC 

input 

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

output 

AABB 
AACC 
BCDD 
BCDD 

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 

출처: coci 2008/2009 contest3 4/6
▒대회 제한시간은 0.3 초 입니다.
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]