대칭 행렬

행렬은 문자로 채워진 직사각형 표입니다. 행과 열의 수가 같은 행렬을 정사각형 행렬이라고 합니다. 정사각형 행렬 M이 모든 i, j에 대해 M_{i,j} = M_{j,i}를 만족하면 M은 대칭 행렬입니다.

다음 두 행렬은 대칭 행렬입니다.

AAB        AAA
ACC        ABA
BCC        AAA

다음 두 행렬은 대칭 행렬이 아닙니다.

ABCD        AAB
ABCD        ACA
ABCD        DAA
ABCD

사용할 수 있는 문자와 각 문자의 개수가 주어집니다. 모든 문자를 정확히 한 번씩 사용해서 만들 수 있는 대칭 행렬 중 사전순으로 가장 앞서는 행렬을 고른 뒤, 그 행렬에서 지정된 열만 남긴 열 부분집합을 출력하세요.

행렬의 열 부분집합은 일부 열만 남기고 나머지 열을 지운 행렬입니다. 예를 들어 다음 행렬을 보겠습니다.

AAB
ACC
BCC

1번 열과 3번 열만 남기면 다음과 같습니다.

AB
AC
BC

행렬의 사전순은 행을 위에서 아래로, 각 행을 왼쪽에서 오른쪽으로 이어 붙인 문자열의 사전순과 같습니다.

첫째 줄에 두 정수 N과 K가 주어집니다. N은 행렬의 크기이고, K는 사용할 수 있는 서로 다른 문자의 개수입니다. (1 <= N <= 30000, 1 <= K <= 26)

다음 K개 줄에는 사용할 수 있는 문자와 그 개수가 공백으로 구분되어 주어집니다. 문자는 모두 알파벳 대문자입니다. 예를 들어 A 3은 A를 3번 사용할 수 있다는 뜻입니다.

사용할 수 있는 문자의 총개수는 정확히 N^2개입니다.

다음 줄에는 열 부분집합의 크기 P가 주어집니다. (1 <= P <= 50)

마지막 줄에는 열 부분집합에 포함할 P개의 열 번호가 주어집니다. 각 번호는 1 이상 N 이하이고, 오름차순이며, 중복되지 않습니다.

주어진 문자로 대칭 행렬을 만들 수 있다면, 사전순으로 가장 앞서는 대칭 행렬에서 지정된 열만 남긴 열 부분집합을 출력합니다.

대칭 행렬을 만들 수 없다면 IMPOSSIBLE을 출력합니다.