Problem Description

You need to construct an $n \times n$ character matrix $M$.

This character matrix has the following constraints:
1. $M_{i,j} = M_{j,i} (1 \le i,j \le n)$.
2. It must contain exactly $a_i$ instances of the character $c_i$.

Since there are many possible constructions, you need to output the lexicographically smallest one.

Due to the large amount of output, you only need to output $p$ columns, as specified in the input format.

If there is no solution, output IMPOSSIBLE.

Input Format

The first line contains two integers $n$ and $k$, where $k$ is the number of constraints of type 2.

The next $k$ lines each contain a capital letter and an integer, representing $c_i$ and $a_i$ respectively.

The next line contains an integer $p$.

The next line contains $p$ integers, representing the column indices you need to output, guaranteed to be in ascending order.

Output Format

Output an $n$ row by $p$ column character matrix. If there is no solution, output IMPOSSIBLE.

Sample Input and Output

Sample Input #1

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

Sample Output #1

AAB
ACC
BCC 

Sample Input #2

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

Sample Output #2

AABB
AACC
BCDD
BCDD 

Sample Input #3

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

Sample Output #3

AC
BE
DE
ED 

Sample Input #4

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

Sample Output #4

IMPOSSIBLE 

Notes

Data Range and Constraints

• For $60\%$ of the data, $n \le 300$.
• For $80\%$ of the data, $n \le 3 \times 10^3$.
• For $100\%$ of the data, $1 \le n \le 3 \times 10^4$, $1 \le k \le 26$, $\sum a_i = n^2$, $c_i \neq c_j$, $1 \le p \le 50$.

Notes

This problem is translated from the Croatian Open Competition in Informatics 2008/2009 Contest #3 T4 MATRICA.

见题面 Input 部分

见题面 Output 部分