Matrica

행렬은 글자들의 직사각형 표이다. 정사각 행렬은 행과 열의 수가 같은 행렬이다. 정사각 행렬 \(M\)의 글자들이 주대각선에 대해 대칭이면(모든 \(i\), \(j\) 쌍에 대해 \(M_{ij} = M_{ji}\)) 그 행렬을 대칭 행렬이라고 한다.

대칭 행렬 두 개:

AAB    AAA
ACC    ABA
BCC    AAA

대칭이 아닌 행렬 두 개:

ABCD   AAB
ABCD   ACA
ABCD   DAA
ABCD

사용할 수 있는 글자들의 모음이 주어졌을 때, 그 글자들을 모두 사용하여 만들 수 있는 사전순으로 가장 앞서는 대칭 행렬에서, 지정된 열들의 부분집합을 출력해야 한다.

그런 행렬이 존재하지 않으면 IMPOSSIBLE을 출력한다.

행렬 \(A\)가 행렬 \(B\)보다 사전순으로 앞서는지 판단하려면, 원소들을 행 우선 순서로(모든 행을 이어 붙여 긴 문자열을 만든 것처럼) 생각한다. 두 행렬이 처음으로 다른 원소가 \(A\)에서 더 작으면 \(A\)가 \(B\)보다 사전순으로 앞선다.

입력의 첫째 줄에 두 정수 \(N\) (\(1 \le N \le 30000\))과 \(K\) (\(1 \le K \le 26\))가 주어진다. \(N\)은 행렬의 크기이고, \(K\)는 나타나는 서로 다른 글자의 수이다.

다음 \(K\)개의 줄에는 대문자 하나와 양의 정수 하나가 공백으로 구분되어 주어진다. 이 정수는 해당 글자를 몇 개 사용해야 하는지를 나타낸다. 예를 들어 어떤 줄에 "A 3"이라고 되어 있으면 글자 A는 출력 행렬에 세 번 나타나야 한다. 글자의 총수는 정확히 \(N^2\)이다. 같은 글자가 입력에 두 번 이상 나타나지는 않는다.

다음 줄에 출력해야 하는 열의 수인 정수 \(P\) (\(1 \le P \le 50\))가 주어진다.

마지막 줄에 정수 \(P\)개, 즉 출력해야 하는 열들의 번호가 주어진다. 번호는 \(1\) 이상 \(N\) 이하이며, 오름차순으로 중복 없이 주어진다.

주어진 글자 모음으로 대칭 행렬을 만들 수 있으면, 요구된 열들을 \(N\)개의 줄에, 각 줄에 \(P\)개의 문자를 공백 없이 출력한다. 그렇지 않으면 IMPOSSIBLE(따옴표는 표기의 명확성을 위한 것)을 출력한다.

채점: 전체 점수의 \(60\%\)에 해당하는 테스트 케이스에서는 \(N\)이 최대 \(300\)이다. 전체 점수의 \(80\%\)에 해당하는 테스트 케이스에서는 \(N\)이 최대 \(3000\)이다.

riseoj 작성

출처 COCI 2008/2009 Contest 3