Ma trận kí tự là một bảng hình chữ nhật gồm ~m \times n~ kí tự được viết thành ~m~ dòng và ~n~ cột. Ma trận vuông là ma trận có số dòng và số cột bằng nhau. Ma trận kí tự ~M~ gọi là ma trận đối xứng nếu ~M~ là ma trận vuông và các phần tử của ma trận đối xứng qua đường chéo chính (đường chéo chính của một ma trận ~A~ bao gồm các phần tử ~A_{i,j}~ với ~i=j~).
Dưới đây là minh họa cho ma trận kí tự đối xứng và ma trận kí tự không đối xứng:
A
A
B
A
C
C
B
C
C
Ma trận đối xứng
A
A
B
A
C
A
D
A
A
Ma trận không đối xứng
Ma trận kí tự ~A~ có thứ tự từ điển nhỏ hơn ma trận kí tự ~B~ nếu ghép tất cả các phần tử của ma trận theo thứ tự từ trái sang phải, từ trên xuống dưới thành một xâu dài thì xâu ghép được từ ma trận ~A~ có thứ tự từ điển nhỏ hơn xâu ghép được từ ma trận ~B~.
Cho trước một tập kí tự, hãy xây dựng ma trận kí tự đối xứng có thứ tự từ điển nhỏ nhất, tuy nhiên chỉ cần đưa ra một số cột của ma trận xây dựng được.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên ~N~ (~1 \leq N \leq 30000~) và ~K~ (~1 \leq K \leq 26~). ~N~ là kích thước của ma trận, ~K~ là số kí tự xuất hiện trong ma trận.
Mỗi dòng trong ~K~ dòng tiếp theo chứa một kí tự chữ cái in hoa và một số nguyên dương phân cách nhau bởi dấu cách. Số nguyên kí hiệu số lượng kí tự tương ứng dùng để xây dựng ma trận đối xứng. Ví dụ: A 3
nghĩa là kí tự A
xuất hiện 3 lần trong ma trận đối xứng sẽ xây dựng.
Dữ liệu vào đảm bảo các kí tự chỉ xuất hiện một lần và tổng số kí tự được cho bằng ~N^2~.
Dòng tiếp theo chứa số nguyên ~P~ (~1 \leq P \leq 50~), số lượng cột cần được đưa ra.
Dòng cuối cùng chứa ~P~ số nguyên phân biệt, chỉ số của cột phải đưa ra. Mỗi số có giá trị từ trong đoạn từ ~1~ đến ~N~, được viết theo thứ tự tăng.
Dữ liệu ra
Nếu có thể xây dựng được ma trận đối xứng thì đưa ra các phần tử của ~K~ cột theo yêu cầu từ dữ liệu vào, mỗi cột gồm ~N~ dòng, các kí tự trên dòng viết liền nhau (không chứa dấu cách).
Ngược lại, ghi ra xâu IMPOSSIBLE
.
Sample Input 1
4 5
E 4
A 3
B 3
C 3
D 3
2
2 4
Sample Output 1
AC
BE
DE
ED
Sample Input 2
4 6
F 1
E 3
A 3
B 3
C 3
D 3
4
1 2 3 4
Sample Output
IMPOSSIBLE
Comments