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
The following figure shows two symmetric matrices and one which is not symmetric:
AAB AAA
ACC ABA
BCC AAA
Two symmetric matrices.
ABCD AAB
ABCD ACA
ABCD DAA
ABCD
Two 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
Input Specification
The first line of input contains two integers
Each of the following A 3
,
then the letter
The total number of letters will be exactly
Output Specification
If it is possible to compose a symmetric matrix from the given collection of letters, output the required
columns on IMPOSSIBLE
.
Scoring
In test cases worth
Sample Input 1
3 3
A 3
B 2
C 4
3
1 2 3
Sample Output 1
AAB
ACC
BCC
Sample Input 2
4 4
A 4
B 4
C 4
D 4
4
1 2 3 4
Sample Output 2
AABB
AACC
BCDD
BCDD
Sample Input 3
4 5
E 4
A 3
B 3
C 3
D 3
2
2 4
Sample Output 3
AC
BE
DE
ED
Sample Input 4
4 6
F 1
E 3
A 3
B 3
C 3
D 3
4
1 2 3 4
Sample Output 4
IMPOSSIBLE
Comments