시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB504316.667%

문제

구역의 경계가 주어졌을 때, 각 구역을 채우는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러개가 주어진다. 각 테스트 케이스의 첫째 줄에는 행의 개수 R, 열의 개수 C, 구역의 개수가 주어진다. 행은 제일 위가 1행이고, 열은 가장 왼쪽이 1열이다. 행은 최대 47행이고, 열은 최대 63행이다.

다음 둘째 줄부터는 각 구역의 설명이 주어진다. 구역의 설명의 첫째 줄에는 구역을 채우는데 사용할 알파벳, 시작하는 행 번호와 열 번호, 경계선의 개수가 주어진다. 경계선의 개수는 적어도 두 개이다. 알파벳은 중복되지 않으며, 다음 줄은 경계선을 설명하는 줄이다.

H A B
G   C
F E D

위와 같이 경계선을 시작점부터 시계방향으로 설명한다.

출력

각각의 테스트 케이스에 대해서, R개의 행, C개의 열로 구역을 모두 채운 결과를 출력한다. 구역이 아닌 곳은 마침표('.')로 출력한다.

다음과 같은 경우가 발생할 때는, 발생한 순서대로 구역을 채운 결과를 출력하기 전에 한 줄에 하나씩 출력한다. (아래 설명에서 A와 B는 해당하는 구역 알파벳으로 바꾸면 된다)

1. 경계선이 배열의 경계를 넘어갈 때는 다음과 같이 출력한다.

REGION A GOES OUTSIDE THE ARRAY

2. 경계선이 닫혀있지 않다면 다음과 같이 출력한다. 즉, 다시 시작점으로 돌아오지 않았을 때이다.

REGION A BOUNDARY IS NOT CLOSED

3. 구역 B의 경계가 이전에 채운 구역 A와 겹친다면, 다음과 같이 출력한다.

REGION B BOUNDARY INTERSECTS REGION A

각 테스트 케이스는 빈 줄로 구분한다.

예제 입력 1

2
20 40 4
B 3 21 22
CCDDDCBBBCCFFFFFGHHHHH
C 5 8 36
CCDCDDDEDEEFEFFFGFGGHGHHHAHAABABBBCB
D 10 24 38
CCCCCCEEEGGFEDCCEEEGGGGGGAAACCBAHGGAAA
A 2 2 3
CEH
10 20 4
A 4 6 10
GGAAACCEEE
B 6 16 30
CCCCCCCCCCCCEEEGGGGGGGGGGGGAAA
C 5 6 10
CCCCDDFFFG
D 6 2 10
AAACCEEEGG

예제 출력 1

........................................
.AA.....................................
..A.................BBB......BBB........
.....................BBB....BBB.........
.......CCC............BBB..BBB..........
.....CCCCCCC...........BBBBBB...........
....CCCCCCCCC...........BBBB............
...CCCCCCCCCCC...........BB.............
..CCCCCCCCCCCCC.........................
..CCCCCCCCCCCCC........DDDDDDD..........
.CCCCCCCCCCCCCCC.......DDDDDDD..........
.CCCCCCCCCCCCCCC.......DDDDDDD..........
.CCCCCCCCCCCCCCC.......DDDDDDD..........
..CCCCCCCCCCCCC...........D.............
..CCCCCCCCCCCCC...........D.............
...CCCCCCCCCCC.........DDDDDDD..........
....CCCCCCCCC..........DDDDDDD..........
.....CCCCCCC...........DDDDDDD..........
.......CCC.............DDDDDDD..........
........................................

REGION B GOES OUTSIDE THE ARRAY
REGION C BOUNDARY IS NOT CLOSED
REGION D BOUNDARY INTERSECTS REGION A
...AAA..............
...AAA..............
...AAA..............
...AAA..............
....................
....................
....................
....................
....................
....................
W3sicHJvYmxlbV9pZCI6IjI3NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmNcdWM1ZWQgXHVjYzQ0XHVjNmIwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWFkNmNcdWM1ZWRcdWM3NTggXHVhY2JkXHVhY2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMSBcdWFkNmNcdWM1ZWRcdWM3NDQgXHVjYzQ0XHVjNmIwXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1Yzc1OCBcdWFjMWNcdWMyMTggUiwgXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOCBDLCBcdWFkNmNcdWM1ZWRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTg5XHVjNzQwIFx1YzgxY1x1Yzc3YyBcdWM3MDRcdWFjMDAgMVx1ZDU4OVx1Yzc3NFx1YWNlMCwgXHVjNWY0XHVjNzQwIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM3NzQgMVx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVkNTg5XHVjNzQwIFx1Y2Q1Y1x1YjMwMCA0N1x1ZDU4OVx1Yzc3NFx1YWNlMCwgXHVjNWY0XHVjNzQwIFx1Y2Q1Y1x1YjMwMCA2M1x1ZDU4OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzBcdWIyOTQgXHVhYzAxIFx1YWQ2Y1x1YzVlZFx1Yzc1OCBcdWMxMjRcdWJhODVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkNmNcdWM1ZWRcdWM3NTggXHVjMTI0XHViYTg1XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjNTRjXHVkMzBjXHViY2IzLCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVkNTg5IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWM1ZjQgXHViYzg4XHVkNjM4LCBcdWFjYmRcdWFjYzRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhY2JkXHVhY2M0XHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHViNDUwIFx1YWMxY1x1Yzc3NFx1YjJlNC4gXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQwIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM3NDAgXHVhY2JkXHVhY2M0XHVjMTIwXHVjNzQ0IFx1YzEyNFx1YmE4NVx1ZDU1OFx1YjI5NCBcdWM5MDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkggQSBCXHJcbkcgICBDXHJcbkYgRSBEPFwvcHJlPlxyXG5cclxuPHA+XHJcblx0XHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFjYmRcdWFjYzRcdWMxMjBcdWM3NDQgXHVjMmRjXHVjNzkxXHVjODEwXHViZDgwXHVkMTMwIFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWMxMjRcdWJhODVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBSXHVhYzFjXHVjNzU4IFx1ZDU4OSwgQ1x1YWMxY1x1Yzc1OCBcdWM1ZjRcdWI4NWMgXHVhZDZjXHVjNWVkXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWNjNDRcdWM2YjQgXHVhY2IwXHVhY2ZjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZDZjXHVjNWVkXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFjZjNcdWM3NDAgXHViOWM4XHVjZTY4XHVkNDVjKCYjMzk7LiYjMzk7KVx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU2MCBcdWI1NGNcdWIyOTQsIFx1YmMxY1x1YzBkZFx1ZDU1YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhZDZjXHVjNWVkXHVjNzQ0IFx1Y2M0NFx1YzZiNCBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWM1NDRcdWI3OTggXHVjMTI0XHViYTg1XHVjNWQwXHVjMTFjIEFcdWM2NDAgQlx1YjI5NCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVhZDZjXHVjNWVkIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1YzczY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWJhNzQgXHViNDFjXHViMmU0KTxcL3A+XHJcblxyXG48cD5cclxuXHQxLiBcdWFjYmRcdWFjYzRcdWMxMjBcdWM3NzQgXHViYzMwXHVjNWY0XHVjNzU4IFx1YWNiZFx1YWNjNFx1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDggXHViNTRjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdFJFR0lPTiBBIEdPRVMgT1VUU0lERSBUSEUgQVJSQVk8XC9wPlxyXG5cclxuPHA+XHJcblx0Mi4gXHVhY2JkXHVhY2M0XHVjMTIwXHVjNzc0IFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHViMmU0XHVjMmRjIFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWM5YzAgXHVjNTRhXHVjNTU4XHVjNzQ0IFx1YjU0Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cclxuXHRSRUdJT04gQSBCT1VOREFSWSBJUyBOT1QgQ0xPU0VEPFwvcD5cclxuXHJcbjxwPlxyXG5cdDMuIFx1YWQ2Y1x1YzVlZCBCXHVjNzU4IFx1YWNiZFx1YWNjNFx1YWMwMCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVjYzQ0XHVjNmI0IFx1YWQ2Y1x1YzVlZCBBXHVjNjQwIFx1YWNiOVx1Y2U1Y1x1YjJlNFx1YmE3NCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0UkVHSU9OIEIgQk9VTkRBUlkgSU5URVJTRUNUUyBSRUdJT04gQTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWJlNDggXHVjOTA0XHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmVnaW9uIEZJbGxpbmciLCJkZXNjcmlwdGlvbiI6IjxwPlRoaXMgcHJvYmxlbSBpcyB0byB3cml0ZSBhIHByb2dyYW0gdG8gZmlsbCBhIHJlZ2lvbiBpbiBhIHJlY3Rhbmd1bGFyIGFycmF5IG9mIHBpeGVscyBnaXZlbiB0aGUgb3V0bGluZSBvZiB0aGUgcmVnaW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgcHJvYmxlbSBpbnN0YW5jZXMuIEVhY2ggcHJvYmxlbSBpbnN0YW5jZSBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgcm93LWNvdW50IG9mIHRoZSBhcnJheSwgdGhlIGNvbHVtbi1jb3VudCBvZiB0aGUgYXJyYXkgYW5kIHRoZSBudW1iZXItb2YtcmVnaW9ucyB0byBmaWxsIGFzIGRlY2ltYWwgaW50ZWdlcnMuIFJvd3MgYXJlIGNvdW50ZWQgZnJvbSB0b3AgdG8gYm90dG9tIGJlZ2lubmluZyB3aXRoIDEuIENvbHVtbnMgYXJlIGNvdW50ZWQgZnJvbSBsZWZ0IHRvIHJpZ2h0IGJlZ2lubmluZyB3aXRoIDEuIFRoZSBpbnB1dCBlbmRzIHdpdGggYSByb3ctY291bnQgb2YgMC4gUm93LWNvdW50IHdpbGwgYmUgYXQgbW9zdCA0NyBhbmQgY29sdW1uLWNvdW50IHdpbGwgYmUgYXQgbW9zdCA2My4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBwcm9ibGVtIGluc3RhbmNlIGlzIGZvbGxvd2VkIGJ5IHJlZ2lvbiBkZXNjcmlwdGlvbnMgZm9yIG51bWJlci1vZi1yZWdpb25zIHJlZ2lvbnMuIEVhY2ggcmVnaW9uIGRlc2NyaXB0aW9uIGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nOiBhIHNpbmdsZSBjaGFyYWN0ZXIgdG8gYmUgdXNlZCB0byBmaWxsIHRoZSByZWdpb24sIHRoZSByb3cgbnVtYmVyIG9mIHRoZSBzdGFydCBwaXhlbCwgdGhlIGNvbHVtbiBudW1iZXIgb2YgdGhlIHN0YXJ0IHBpeGVsIGFuZCB0aGUgbnVtYmVyIG9mIHBpeGVscyBpbiB0aGUgYm91bmRhcnkgd2hpY2ggd2lsbCBhbHdheXMgYmUgYXQgbGVhc3QgdHdvLiBUaGUgcmVnaW9uIGZpbGwgY2hhcmFjdGVyIHdpbGwgYmUgZGlzdGluY3QgZm9yIGVhY2ggcmVnaW9uIHdpdGhpbiBhIHByb2JsZW0gaW5zdGFuY2UuIFRoaXMgbGluZSBpcyBmb2xsb3dlZCBieSBsaW5lcyBvZiBkaXJlY3Rpb24gY29kZXMgKHVwID0gQSwgdXAgcmlnaHQgPSBCLCBldGMuKTombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuSCBBIEJcclxuRyAgIENcclxuRiBFIEQ8XC9wcmU+XHJcblxyXG48cD5kZXNjcmliaW5nIHRoZSBvdXRsaW5lIHRyYXZlcnNlZCBjbG9ja3dpc2UuIFRoZSBzdGFydCBwaXhlbCBtYXkgYmUgYW55IHBvaW50IG9uIHRoZSBvdXRsaW5lLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHByb2JsZW0gaW5zdGFuY2UsIHRoZSBvdXRwdXQgY29uc2lzdHMgb2Ygcm93LWNvdW50IGxpbmVzIG9mIGNvbHVtbi1jb3VudCBjaGFyYWN0ZXJzIGVhY2ggb2Ygd2hpY2ggaXMgZWl0aGVyIGEgcGVyaW9kICguKSBpbmRpY2F0aW5nIHRoYW4gbm8gcmVnaW9uIGluY2x1ZGVzIHRoYXQgcGl4ZWwgb3IgdGhlIGZpbGwgY2hhcmFjdGVyIG9mIHRoZSByZWdpb24gd2hpY2ggaW5jbHVkZXMgdGhhdCBwaXhlbC4gVGhlIHJvd2NvdW50IGxpbmVzIGFyZSBmb2xsb3dlZCBieSBhIHNpbmdsZSBibGFuayBsaW5lLiBUaGlzIGFycmF5IG1heSBiZSBwcmVjZWRlZCBieSBvbmUgb3IgbW9yZSBsaW5lcyBvZiB0aGUgZm9sbG93aW5nIGZvcm0gKHdoZXJlIEEgb3IgQiBhcmUgdGhlIGZpbGwgY2hhcmFjdGVycyBzcGVjaWZpZWQgaW4gdGhlIHJlZ2lvbiBoZWFkZXIpOjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlJFR0lPTiBBIEdPRVMgT1VUU0lERSBUSEUgQVJSQVkmbmJzcDs8XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPklmIHRoZSBib3VuZGFyeSBwYXRoIGdvZXMgb3V0c2lkZSB0aGUgYm91bmRhcmllcyBvZiB0aGUgYXJyYXkgc3BlY2lmaWVkIGZvciB0aGUgcHJvYmxlbSBpbnN0YW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5SRUdJT04gQSBCT1VOREFSWSBJUyBOT1QgQ0xPU0VEJm5ic3A7PFwvc3Ryb25nPjxcL3A+XHJcblxyXG48cD5JZiB0aGUgYm91bmRhcnkgYXMgc3BlY2lmaWVkIGRvZXMgbm90IHJldHVybiB0byB0aGUgc3RhcnQgcG9pbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+UkVHSU9OIEIgQk9VTkRBUlkgSU5URVJTRUNUUyBSRUdJT04gQSZuYnNwOzxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+SWYgdGhlIGJvdW5kYXJ5IG9mIHJlZ2lvbiBCIGNvbnRhaW5zIHBvaW50cyBvZiBhIHByZXZpb3VzbHkgc3BlY2lmaWVkIHJlZ2lvbi4gSWYgYSBwcmV2aW91cyByZWdpb24gZmFpbHMgYW55IG9mIHRoZXNlIHRlc3RzIGl0IGlzIG5vdCBjb25zaWRlcmVkIGZvciBpbnRlcnNlY3Rpb24gd2l0aCBmb2xsb3dpbmcgcmVnaW9ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggcmVnaW9uLCB0aGUgZmlyc3QgY29uZGl0aW9uIHRvIGJlIHZpb2xhdGVkIGlzIHRvIGJlIGRpc3BsYXllZC4gQW55IHJlZ2lvbiBmb3Igd2hpY2ggYW4gZXJyb3IgbGluZSBpcyBnaXZlbiB3aWxsIG5vdCBiZSBmaWxsZWQgaW4gdGhlIHJlY3Rhbmd1bGFyIGFycmF5PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==