대칭 행렬

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

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

AAB        AAAACC        ABABCC        AAA

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

ABCD        AABABCD        ACAABCD        DAAABCD

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

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

AABACCBCC

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

ABACBC

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

첫째 줄에 두 정수 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을 출력합니다.