P6411 [COCI 2008/2009 #3] MATRICA

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)$. 1. 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`.

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 an $n$-row, $p$-column character matrix. If there is no solution, output `IMPOSSIBLE`.

#### 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](https://hsin.hr/coci/archive/2008_2009) [Contest #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf). Translated by ChatGPT 5