### COCI 2008/2009, Contest #3

## Task MATRICA

A matrix is a rectangular table of letters. A square matrix has 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_{ij} = M_{ji} for all pairs of i and j).

The following figure shows two symmetric matrices and one which is not symmetric:

AAB AAA ACC ABA BCC AAATwo symmetric matrices. |
ABCD AAB ABCD ACA ABCD DAA ABCDTwo matrices that are not symmetric. |

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 rowmajor 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.

### Input

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.

### Output

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).### Scoring

In test cases worth 60% of points, N will be at most 300.In test cases worth 80% of points, N will be at most 3000.

### Examples

## Input3 3 A 3 B 2 C 4 3 1 2 3 ## OutputAAB ACC BCC |
## Input4 4 A 4 B 4 C 4 D 4 4 1 2 3 4 ## OutputAABB AACC BCDD BCDD |
## Input4 5 E 4 A 3 B 3 C 3 D 3 2 2 4 ## OutputAC BE DE ED |
## Input4 6 F 1 E 3 A 3 B 3 C 3 D 3 4 1 2 3 4 ## OutputIMPOSSIBLE |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 32M

**Added:** Dec 14, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

taimla101on Dec 14, 2008 - 1:42:13 pm UTC I dont get why the third test case workshansonw1on Dec 14, 2008 - 3:11:12 pm UTC Re: I dont get why the third test case works