### 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 N2. 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