Lexicographically Smallest Symmetric Character Matrix

You are given a positive integer $n$, an integer $p$, and $k$ different characters with their counts. Your task is to construct an $n\times n$ character matrix $M$ satisfying the following conditions:

1. The matrix is symmetric, i.e. $M_{i,j}=M_{j,i}$ for all $1\le i,j\le n$.
2. The matrix contains exactly $a_i$ copies of character $c_i$ for each $i$ ($1\le i\le k$), and ( \sum_{i=1}^{k} a_i = n^2 ).

Among all possible matrices, you must output the one that is lexicographically smallest (i.e. if the matrix is read row‐by‐row, the resulting string is minimum in lexicographical order).

Note that printing the full $n\times n$ matrix might be too much. Hence, you are only required to output the first $p$ columns of the matrix.

If no valid matrix exists, print IMPOSSIBLE.

---

Construction idea and mathematical formulation

Because the matrix is symmetric, the diagonal cells $M_{i,i}$ appear only once while every off-diagonal cell is paired with its symmetric counterpart. In a valid solution, if a character $c$ appears in the diagonal $d_c$ times, then the remaining $a_c-d_c$ occurrences must be even (since they are placed in pairs). Further, if $a_c$ is odd then $d_c$ must be odd, and if $a_c$ is even then $d_c$ must be even.

Let the number of diagonal cells be $n$. First, assign the mandatory diagonal counts: for each character $c$, if $a_c$ is odd then assign one occurrence in the diagonal. Let $\text{odd}\_count$ be the total number of such mandatory assignments. The remaining diagonal positions, say $\text{extra} = n - \text{odd\_count}$, have to be filled with letters in pairs (i.e. 2 at a time from the same character) so that the leftover counts (assigned to off-diagonals) remain even.

The lexicographically smallest solution is obtained by choosing the smallest possible letter for each position (first on diagonals in increasing order of indices, and then for each off-diagonal pair in lexicographical order).

---

Input/Output Format

The input format is as follows:

n p k
c1 a1
c2 a2
... 
ck ak

Here, $n$ and $p$ are positive integers, and $k$ is the number of distinct characters. For each of the next $k$ lines, a character and its count are provided. It is guaranteed that ( \sum_{i=1}^{k} a_i = n^2 ).

The output format is as follows:

• If a valid matrix exists, output $n$ lines; each line is a string of length $p$ representing the first $p$ columns of that row of the matrix.
• Otherwise, output a single line with IMPOSSIBLE.

inputFormat

The first line contains three integers: n, p, and k, where n is the size of the matrix, p is the number of columns to output (p ≤ n), and k is the number of distinct characters.

Then follow k lines. Each of these lines contains a character and an integer a, meaning that character appears exactly a times in the matrix. It is guaranteed that \( \sum_{i=1}^k a = n^2 \).

outputFormat

If a valid symmetric matrix satisfying the given constraints exists, output n lines where each line is the concatenation of the first p characters of that row. Otherwise, output a single line with the string "IMPOSSIBLE".

sample

3 2 2
A 5
B 4

AA
AA
BB

</p>