시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 6 6 66.667%

문제

행렬은 글자로 채워져 있는 직사각형 표이다. 정사각형 행렬은 열의 수와 행의 수가 같을 때이다. 정사각형 행렬 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
W3sicHJvYmxlbV9pZCI6IjI5NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWNlNmQgXHVkNTg5XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1ODlcdWI4MmNcdWM3NDAgXHVhZTAwXHVjNzkwXHViODVjIFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDQ1Y1x1Yzc3NFx1YjJlNC4gXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDU4OVx1YjgyY1x1Yzc0MCBcdWM1ZjRcdWM3NTggXHVjMjE4XHVjNjQwIFx1ZDU4OVx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQ0IFx1YjU0Y1x1Yzc3NFx1YjJlNC4gXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDU4OVx1YjgyYyBNXHVjNzc0IFx1YjMwMFx1Y2U2ZFx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHViYWE4XHViNGUwIGksalx1YzMwZFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgTTxzdWI+aWo8XC9zdWI+ID0gTTxzdWI+amk8XC9zdWI+XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWI0NTAgXHVkNTg5XHViODJjXHVjNzQwIFx1YjMwMFx1Y2U2ZFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkFBQiAgICAgICAgQUFBXHJcbkFDQyAgICAgICAgQUJBXHJcbkJDQyAgICAgICAgQUFBPFwvcHJlPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YjQ1MCBcdWQ1ODlcdWI4MmNcdWM3NDAgXHViMzAwXHVjZTZkXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkFCQ0QgICAgICAgIEFBQlxyXG5BQkNEICAgICAgICBBQ0FcclxuQUJDRCAgICAgICAgREFBXHJcbkFCQ0Q8XC9wcmU+XHJcblxyXG48cD5cdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjMGFjXHVjNmE5XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjMwMFx1Y2U2ZFx1ZDU4OVx1YjgyYyBcdWM5MTFcdWM1ZDBcdWMxMWMsIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM1NWVcdWMxMWNcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc3NFx1Yjc4MCBcdWQyYjlcdWM4MTUgXHVjNWY0XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjOWMwXHVjNmNjXHViYzg0XHViOWIwIFx1ZDU4OVx1YjgyY1x1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ1ODlcdWI4MmNcdWM3NDQgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cHJlPlxyXG5BQUJcclxuQUNDXHJcbkJDQzxcL3ByZT5cclxuXHJcbjxwPlx1YzcwNCBcdWQ1ODlcdWI4MmNcdWM3NTggMSwzXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiAoMlx1YzVmNFx1YzVkMCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWM5YzBcdWM2Y2NcdWJjODRcdWI5YWNcdWJhNzQgXHViNDFjXHViMmU0Lik8XC9wPlxyXG5cclxuPHByZT5cclxuQUJcclxuQUNcclxuQkM8XC9wcmU+XHJcblxyXG48cD5cdWI0NTAgXHVkNTg5XHViODJjIEFcdWM2NDAgQlx1Yjk3YyBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHViZTQ0XHVhZDUwXHVkNTU4XHViODI0XHViYTc0LCBcdWFjMDEgXHVkNTg5XHViODJjXHVjNzQ0IFx1ZDU4OVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYWE4XHViNDUwIFx1Yzc3NFx1YzViNFx1YmQ5OVx1YzVlYyBcdWFlMzQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjljY1x1YjRlMCBcdWI0YTQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YmU0NFx1YWQ1MFx1Yjk3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWM3NzRcdWFjZTAsIEtcdWIyOTQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAzMDAwMCwgMSAmbGU7IEsgJmxlOyAyNik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIEtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWFkZjggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWIyOTQgXHViYWE4XHViNDUwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICZxdW90O0EgMyZxdW90O1x1Yzc0MCBBXHViOTdjIDNcdWJjODggXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBOPHN1cD4yPFwvc3VwPlx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5XHVjNzU4IFx1ZDA2Y1x1YWUzMCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBQICZsZTsgNTApPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQsIFBcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3M2NcdWJhNzAsIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWM5MTFcdWJjZjVcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWI4NWMgXHViMzAwXHVjZTZkXHVkNTg5XHViODJjXHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0LCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0ICZxdW90O0lNUE9TU0lCTEUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHViNTMwXHVjNjM0XHVkNDVjXHViMjk0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BVFJJQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbWF0cml4IGlzIGEgcmVjdGFuZ3VsYXIgdGFibGUgb2YgbGV0dGVycy4gQSBzcXVhcmUgbWF0cml4IGlzIGEgbWF0cml4IHdpdGggYW4gZXF1YWwgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMuIEEgc3F1YXJlIG1hdHJpeCBNIGlzIGNhbGxlZCBzeW1tZXRyaWMgaWYgaXRzIGxldHRlcnMgYXJlIHN5bW1ldHJpYyB3aXRoIHJlc3BlY3QgdG8gdGhlIG1haW4gZGlhZ29uYWwgKE1paiA9IE1qaSBmb3IgYWxsIHBhaXJzIG9mIGkgYW5kIGopLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGZpZ3VyZSBzaG93cyB0d28gc3ltbWV0cmljIG1hdHJpY2VzIGFuZCBvbmUgd2hpY2ggaXMgbm90IHN5bW1ldHJpYzombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zeW1tYXRyaXgucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM2cHg7IHdpZHRoOjU1N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgY29sbGVjdGlvbiBvZiBhdmFpbGFibGUgbGV0dGVycywgeW91IGFyZSB0byBvdXRwdXQgYSBzdWJzZXQgb2YgY29sdW1ucyBpbiB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlc3Qgc3ltbWV0cmljIG1hdHJpeCB3aGljaCBjYW4gYmUgY29tcG9zZWQgdXNpbmcgYWxsIHRoZSBsZXR0ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiBubyBzdWNoIG1hdHJpeCBleGlzdHMsIG91dHB1dCAmcXVvdDtJTVBPU1NJQkxFJnF1b3Q7LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UbyBkZXRlcm1pbmUgaWYgbWF0cml4IEEgaXMgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlciB0aGFuIG1hdHJpeCBCLCBjb25zaWRlciB0aGVpciBlbGVtZW50cyBpbiByb3dtYWpvciBvcmRlciAoYXMgaWYgeW91IGNvbmNhdGVuYXRlZCBhbGwgcm93cyB0byBmb3JtIGEgbG9uZyBzdHJpbmcpLiBJZiB0aGUgZmlyc3QgZWxlbWVudCBpbiB3aGljaCB0aGUgbWF0cmljZXMgZGlmZmVyIGlzIHNtYWxsZXIgaW4gQSwgdGhlbiBBIGlzIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXIgdGhhbiBCLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gKDEgJmxlOyBOICZsZTsgMzAwMDApIGFuZCBLICgxICZsZTsgSyAmbGU7IDI2KS4gTiBpcyB0aGUgZGltZW5zaW9uIG9mIHRoZSBtYXRyaXgsIHdoaWxlIEsgaXMgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBsZXR0ZXJzIHRoYXQgd2lsbCBhcHBlYXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBLIGxpbmVzIGNvbnRhaW5zIGFuIHVwcGVyY2FzZSBsZXR0ZXIgYW5kIGEgcG9zaXRpdmUgaW50ZWdlciwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSBpbnRlZ2VyIGRlbm90ZXMgaG93IG1hbnkgY29ycmVzcG9uZGluZyBsZXR0ZXJzIGFyZSB0byBiZSB1c2VkLiBGb3IgZXhhbXBsZSwgaWYgYSBsaW5lIHNheXMgJnF1b3Q7QSAzJnF1b3Q7LCB0aGVuIHRoZSBsZXR0ZXIgQSBtdXN0IGFwcGVhciB0aHJlZSB0aW1lcyBpbiB0aGUgb3V0cHV0IG1hdHJpeC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRvdGFsIG51bWJlciBvZiBsZXR0ZXJzIHdpbGwgYmUgZXhhY3RseSBOPHN1cD4yPFwvc3VwPi4gTm8gbGV0dGVyIHdpbGwgYXBwZWFyIG1vcmUgdGhhbiBvbmNlIGluIHRoZSBpbnB1dC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIFAgKDEgJmxlOyBQICZsZTsgNTApLCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgdGhhdCBtdXN0IGJlIG91dHB1dC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBjb250YWlucyBQIGludGVnZXJzLCB0aGUgaW5kaWNlcyBvZiBjb2x1bW5zIHRoYXQgbXVzdCBiZSBvdXRwdXQuIFRoZSBpbmRpY2VzIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCBOIGluY2x1c2l2ZSwgZ2l2ZW4gaW4gaW5jcmVhc2luZyBvcmRlciBhbmQgd2l0aG91dCBkdXBsaWNhdGVzPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgaXQgaXMgcG9zc2libGUgdG8gY29tcG9zZSBhIHN5bW1ldHJpYyBtYXRyaXggZnJvbSB0aGUgZ2l2ZW4gY29sbGVjdGlvbiBvZiBsZXR0ZXJzLCBvdXRwdXQgdGhlIHJlcXVpcmVkIGNvbHVtbnMgb24gTiBsaW5lcywgZWFjaCBjb250YWluaW5nIFAgY2hhcmFjdGVyLCB3aXRob3V0IHNwYWNlcy4gT3RoZXJ3aXNlLCBvdXRwdXQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90OyAocXVvdGVzIGZvciBjbGFyaXR5KS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #3 4번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: impri