시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 4 4 57.143%

문제

행렬은 글자로 채워져 있는 직사각형 표이다. 정사각형 행렬은 열의 수와 행의 수가 같을 때이다. 정사각형 행렬 M이 대칭이라면, 모든 i,j쌍에 대해서 Mij = Mji를 만족할 때이다.

아래 두 행렬은 대칭인 경우이다.

AAB        AAA
ACC        ABA
BCC        AAA

아래 두 행렬은 대칭이 아닌 경우이다.

ABCD        AAB
ABCD        ACA
ABCD        DAA
ABCD

사용할 수 있는 문자가 주어졌을 때, 이 문자를 모두 사용해서 만들 수 있는 대칭행렬 중에서, 사전순으로 앞서는 행렬의 열의 부분집합을 출력하는 프로그램을 작성하시오.

어떤 행렬의 열의 부분집합이란 특정 열을 제외하고는 모두 지워버린 행렬이다. 아래와 같은 행렬을 살펴보자.

AAB
ACC
BCC

위 행렬의 1,3열의 부분집합은 다음과 같다. (2열에 등장하는 문자를 모두 지워버리면 된다.)

AB
AC
BC

두 행렬 A와 B를 사전순으로 비교하려면, 각 행렬을 행을 순서대로 모두 이어붙여 긴 문자열로 만든 뒤 문자열 비교를 한다고 생각하면 된다.

입력

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

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

사용할 수 있는 문자의 개수는 정확히 N2개이다.

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

마지막 줄에는, P개의 숫자가 주어지고, 열의 부분집합의 내용이다. 각 숫자는 1보다 크거나 같고, N보다 작거나 같으며, 오름차순으로 정렬되어 있고, 중복되지 않는다.

출력

주어진 문자로 대칭행렬을 만드는 것이 가능하다면, 행렬의 열의 부분집합을 출력한다. 만약, 불가능하다면 "IMPOSSIBLE"을 출력한다. (따옴표는 출력하지 않는다)

예제 입력 1

3 3
A 3
B 2
C 4
3
1 2 3

예제 출력 1

AAB
ACC
BCC
W3sicHJvYmxlbV9pZCI6IjI5NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWNlNmQgXHVkNTg5XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQ1ODlcdWI4MmNcdWM3NDAgXHVhZTAwXHVjNzkwXHViODVjIFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDQ1Y1x1Yzc3NFx1YjJlNC4gXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDU4OVx1YjgyY1x1Yzc0MCBcdWM1ZjRcdWM3NTggXHVjMjE4XHVjNjQwIFx1ZDU4OVx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQ0IFx1YjU0Y1x1Yzc3NFx1YjJlNC4gXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDU4OVx1YjgyYyBNXHVjNzc0IFx1YjMwMFx1Y2U2ZFx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHViYWE4XHViNGUwIGksalx1YzMwZFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgTTxzdWI+aWo8XC9zdWI+ID0gTTxzdWI+amk8XC9zdWI+XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yjc5OCBcdWI0NTAgXHVkNTg5XHViODJjXHVjNzQwIFx1YjMwMFx1Y2U2ZFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkFBQiAgICAgICAgQUFBXHJcbkFDQyAgICAgICAgQUJBXHJcbkJDQyAgICAgICAgQUFBPFwvcHJlPlxyXG5cclxuPHA+XHJcblx0XHVjNTQ0XHViNzk4IFx1YjQ1MCBcdWQ1ODlcdWI4MmNcdWM3NDAgXHViMzAwXHVjZTZkXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkFCQ0QgICAgICAgIEFBQlxyXG5BQkNEICAgICAgICBBQ0FcclxuQUJDRCAgICAgICAgREFBXHJcbkFCQ0Q8XC9wcmU+XHJcblxyXG48cD5cclxuXHRcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjMGFjXHVjNmE5XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjMwMFx1Y2U2ZFx1ZDU4OVx1YjgyYyBcdWM5MTFcdWM1ZDBcdWMxMWMsIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM1NWVcdWMxMWNcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzViNFx1YjVhNCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc3NFx1Yjc4MCBcdWQyYjlcdWM4MTUgXHVjNWY0XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjOWMwXHVjNmNjXHViYzg0XHViOWIwIFx1ZDU4OVx1YjgyY1x1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ1ODlcdWI4MmNcdWM3NDQgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cHJlPlxyXG5BQUJcclxuQUNDXHJcbkJDQzxcL3ByZT5cclxuXHJcbjxwPlxyXG5cdFx1YzcwNCBcdWQ1ODlcdWI4MmNcdWM3NTggMSwzXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiAoMlx1YzVmNFx1YzVkMCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWM5YzBcdWM2Y2NcdWJjODRcdWI5YWNcdWJhNzQgXHViNDFjXHViMmU0Lik8XC9wPlxyXG5cclxuPHByZT5cclxuQUJcclxuQUNcclxuQkM8XC9wcmU+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVkNTg5XHViODJjIEFcdWM2NDAgQlx1Yjk3YyBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHViZTQ0XHVhZDUwXHVkNTU4XHViODI0XHViYTc0LCBcdWFjMDEgXHVkNTg5XHViODJjXHVjNzQ0IFx1ZDU4OVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYWE4XHViNDUwIFx1Yzc3NFx1YzViNFx1YmQ5OVx1YzVlYyBcdWFlMzQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjljY1x1YjRlMCBcdWI0YTQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YmU0NFx1YWQ1MFx1Yjk3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVkMDZjXHVhZTMwXHVjNzc0XHVhY2UwLCBLXHViMjk0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYjM4XHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMzAwMDAsIDEgJmxlOyBLICZsZTsgMjYpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM2NDAgXHVhZGY4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAmcXVvdDtBIDMmcXVvdDtcdWM3NDAgQVx1Yjk3YyAzXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggTjJcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWQwNmNcdWFlMzAgUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUCAmbGU7IDUwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0LCBQXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM3NTggXHViMGI0XHVjNmE5XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMjJiXHVjNzkwXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgTlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTcwLCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHViODVjIFx1YjMwMFx1Y2U2ZFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVkNTg5XHViODJjXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCAmcXVvdDtJTVBPU1NJQkxFJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YjUzMFx1YzYzNFx1ZDQ1Y1x1YjI5NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNQVRSSUNBIiwiZGVzY3JpcHRpb24iOiI8cD5BIG1hdHJpeCBpcyBhIHJlY3Rhbmd1bGFyIHRhYmxlIG9mIGxldHRlcnMuIEEgc3F1YXJlIG1hdHJpeCBpcyBhIG1hdHJpeCB3aXRoIGFuIGVxdWFsIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zLiBBIHNxdWFyZSBtYXRyaXggTSBpcyBjYWxsZWQgc3ltbWV0cmljIGlmIGl0cyBsZXR0ZXJzIGFyZSBzeW1tZXRyaWMgd2l0aCByZXNwZWN0IHRvIHRoZSBtYWluIGRpYWdvbmFsIChNaWogPSBNamkgZm9yIGFsbCBwYWlycyBvZiBpIGFuZCBqKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBmaWd1cmUgc2hvd3MgdHdvIHN5bW1ldHJpYyBtYXRyaWNlcyBhbmQgb25lIHdoaWNoIGlzIG5vdCBzeW1tZXRyaWM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3ltbWF0cml4LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzNnB4OyB3aWR0aDo1NTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGNvbGxlY3Rpb24gb2YgYXZhaWxhYmxlIGxldHRlcnMsIHlvdSBhcmUgdG8gb3V0cHV0IGEgc3Vic2V0IG9mIGNvbHVtbnMgaW4gdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0IHN5bW1ldHJpYyBtYXRyaXggd2hpY2ggY2FuIGJlIGNvbXBvc2VkIHVzaW5nIGFsbCB0aGUgbGV0dGVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SWYgbm8gc3VjaCBtYXRyaXggZXhpc3RzLCBvdXRwdXQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG8gZGV0ZXJtaW5lIGlmIG1hdHJpeCBBIGlzIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXIgdGhhbiBtYXRyaXggQiwgY29uc2lkZXIgdGhlaXIgZWxlbWVudHMgaW4gcm93bWFqb3Igb3JkZXIgKGFzIGlmIHlvdSBjb25jYXRlbmF0ZWQgYWxsIHJvd3MgdG8gZm9ybSBhIGxvbmcgc3RyaW5nKS4gSWYgdGhlIGZpcnN0IGVsZW1lbnQgaW4gd2hpY2ggdGhlIG1hdHJpY2VzIGRpZmZlciBpcyBzbWFsbGVyIGluIEEsIHRoZW4gQSBpcyBsZXhpY29ncmFwaGljYWxseSBzbWFsbGVyIHRoYW4gQi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOICgxICZsZTsgTiAmbGU7IDMwMDAwKSBhbmQgSyAoMSAmbGU7IEsgJmxlOyAyNikuIE4gaXMgdGhlIGRpbWVuc2lvbiBvZiB0aGUgbWF0cml4LCB3aGlsZSBLIGlzIHRoZSBudW1iZXIgb2YgZGlzdGluY3QgbGV0dGVycyB0aGF0IHdpbGwgYXBwZWFyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgSyBsaW5lcyBjb250YWlucyBhbiB1cHBlcmNhc2UgbGV0dGVyIGFuZCBhIHBvc2l0aXZlIGludGVnZXIsIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBUaGUgaW50ZWdlciBkZW5vdGVzIGhvdyBtYW55IGNvcnJlc3BvbmRpbmcgbGV0dGVycyBhcmUgdG8gYmUgdXNlZC4gRm9yIGV4YW1wbGUsIGlmIGEgbGluZSBzYXlzICZxdW90O0EgMyZxdW90OywgdGhlbiB0aGUgbGV0dGVyIEEgbXVzdCBhcHBlYXIgdGhyZWUgdGltZXMgaW4gdGhlIG91dHB1dCBtYXRyaXguJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0b3RhbCBudW1iZXIgb2YgbGV0dGVycyB3aWxsIGJlIGV4YWN0bHkgTjxzdXA+MjxcL3N1cD4uIE5vIGxldHRlciB3aWxsIGFwcGVhciBtb3JlIHRoYW4gb25jZSBpbiB0aGUgaW5wdXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBQICgxICZsZTsgUCAmbGU7IDUwKSwgdGhlIG51bWJlciBvZiBjb2x1bW5zIHRoYXQgbXVzdCBiZSBvdXRwdXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGxpbmUgY29udGFpbnMgUCBpbnRlZ2VycywgdGhlIGluZGljZXMgb2YgY29sdW1ucyB0aGF0IG11c3QgYmUgb3V0cHV0LiBUaGUgaW5kaWNlcyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgTiBpbmNsdXNpdmUsIGdpdmVuIGluIGluY3JlYXNpbmcgb3JkZXIgYW5kIHdpdGhvdXQgZHVwbGljYXRlczxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIGl0IGlzIHBvc3NpYmxlIHRvIGNvbXBvc2UgYSBzeW1tZXRyaWMgbWF0cml4IGZyb20gdGhlIGdpdmVuIGNvbGxlY3Rpb24gb2YgbGV0dGVycywgb3V0cHV0IHRoZSByZXF1aXJlZCBjb2x1bW5zIG9uIE4gbGluZXMsIGVhY2ggY29udGFpbmluZyBQIGNoYXJhY3Rlciwgd2l0aG91dCBzcGFjZXMuIE90aGVyd2lzZSwgb3V0cHV0ICZxdW90O0lNUE9TU0lCTEUmcXVvdDsgKHF1b3RlcyBmb3IgY2xhcml0eSkuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d