MATRICA - Matrica

### 题意简述 本题中，一个矩阵是由大写字母组成的表格，而正方形矩阵是长宽相同的矩阵。对称的正方形矩阵就是沿其主对角线对称的正方形矩阵。 比较两个正方形矩阵大小的方式是将其逐行比较大小。比较两行的方式是将其都转换为字符串并按照字典序比较大小。 求最小的对称的正方形矩阵**的某几列**。 ### 输入输出格式 输入数据第一行是正方形矩阵边长 $N(1\leq N \le 30000)$ 和不同的字母数量 $K(1\leq K \leq 26)$。 以下 $K$ 行，每行包括一个大写字母和一个数字 $a$，代表这个字母在矩阵中出现了 $a$ 次。**保证 $\sum a=N^2$ 且没有字母重复出现**。 第 $K+2$ 行是一个整数 $P$ ，代表需要输出 $P$ 列。下一行包含 $P$ 个整数，代表需要输出的每一列。保证该行中所有数均严格单调增且所有数都在 $[1,n]$ 内。 输出包含 $N$ 行，每行 $P$ 个字母，代表所求的 $P$ 列。

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 (M $ _{i,j} $ = M $ _{j,i} $ for all pairs of i and j). For example, the following two matrices are symmetric: ``` AAB AAA ACC ABA BCC AAA ``` However, the following two are not: ``` ABCD AAB ABCD ACA ABCD DAA ABCD ``` 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 row-major 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).

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

AAB
ACC
BCC

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