Description

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

This character matrix must satisfy the following constraints:

1. $M_{i,j} = M_{j,i} \ (1 \le i,j \le n)$.
2. It must contain exactly $a_i$ occurrences of the character $c_i$.

Since there may be many valid constructions, you need to output the lexicographically smallest one.

Because the output would be too large, you only need to output $p$ columns. The exact requirement is stated 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 in constraint 2.

The next $k$ lines each contain an uppercase letter and an integer, which are $c_i$ and $a_i$.

The next line contains an integer $p$.

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

Output Format

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

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 

Hint

Constraints

• For $60\%$ of the testdata, $n \le 300$.
• For $80\%$ of the testdata, $n \le 3 \times 10^3$.
• For $100\%$ of the testdata, $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 T4 MATRICA of Croatian Open Competition in Informatics 2008/2009 Contest #3.

Translated by ChatGPT 5