시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 8 4 3 42.857%

문제

동규는 이번에 새로 나온 그림판 프로그램을 설치했다. 이 프로그램에서 지원하는 색상의 개수는 K개이며, 각 색상은 1부터 K까지 번호가 매겨져 있다. 그림을 그릴 수 있는 캔버스의 크기는 N*N이다. 가장 처음에 모든 칸은 흰색 (1번 색상)으로 칠해져 있다. 이 그림판은 마우스를 이용해서 그림을 그릴 수 없고 키보드로 명령어를 입력해야 한다.

캔버스의 가장 왼쪽 위 칸의 좌표는 (0, 0)이다. 첫 번째 좌표는 x로 행을 나타내고, 두 번째 좌표는 y로 열을 나타낸다.

동규가 가장 좋아하는 그림판 명령어는 PAINT c x1 y1 x2 y2이다. 이 명령어는 선택한 직사각형을 체스판 패턴으로 칠한다. 여기서 c는 색칠할 색상이고, (x1, y1), (x2, y2)는 색칠할 직사각형의 왼쪽 위와 오른쪽 아래 좌표이다.

가장 왼쪽 위 칸의 색상은 명령어에서 고른 색상 c가 된다. 나머지 칸의 색은 체스판 패턴에 의해서 결정된다. 이 때, 색칠되지 않는 칸의 색상은 원래 색상을 그대로 유지한다. 아래 그림은 흰색 캔버스에 빨간 체스판 패턴을 칠했을 때의 모습이다.

그림판에는 두 가지 명령어가 더 있다. 첫 번째는 SAVE로 현재 캔버스를 저장하는 명령이다. 두 번째 명령은 LOAD x로 x번째 저장한 캔버스를 불러오는 명령이다.

하루종일 그림을 그리던 동규는 실수로 저장을 하지 않고 프로그램을 종료했다. 하지만, 이 프로그램은 사용자가 입력한 명령을 순서대로 저장하고 있다. 동규가 입력한 명령을 수행했을 때, 각 칸에 색칠되어 있는 색상을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1000), K(2 ≤ K ≤ 100,000), M(1 ≤ M ≤ 100,000, M은 명령의 개수)이 주어진다.

다음 M개의 줄에는 문제에서 설명한 세 가지 명령어중 하나가 주어진다. 올바르지 않은 명령이 주어지는 경우는 없다.

출력

N개 줄에 각 칸의 색상을 나타내는 N개의 숫자를 출력한다.

예제 입력 1

3 4 7
PAINT 2 0 0 1 1
SAVE
PAINT 3 1 1 2 2
SAVE
PAINT 4 0 2 0 2
LOAD 2
PAINT 4 2 0 2 0

예제 출력 1

2 1 1
1 3 1
4 1 3

힌트

W3sicHJvYmxlbV9pZCI6IjI4NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWFkZGNcdWFjMDAgXHVjMTI0XHVjZTU4XHVkNTVjIFx1YWRmOFx1YjliY1x1ZDMxMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViM2Q5XHVhZGRjXHViMjk0IFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWMwYzhcdWI4NWMgXHViMDk4XHVjNjI4IFx1YWRmOFx1YjliY1x1ZDMxMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTg4XHViMmU0LiBcdWM3NzQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1YzljMFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWMwYzlcdWMwYzFcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IEtcdWFjMWNcdWM3NzRcdWJhNzAsIFx1YWMwMSBcdWMwYzlcdWMwYzFcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBLXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YmNcdWM3NDQgXHVhZGY4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTk0XHViYzg0XHVjMmE0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBOKk5cdWM3NzRcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWNjOThcdWM3NGNcdWM1ZDAgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0MCBcdWQ3NzBcdWMwYzkgKDFcdWJjODggXHVjMGM5XHVjMGMxKVx1YzczY1x1Yjg1YyBcdWNlNjBcdWQ1NzRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViOWJjXHVkMzEwXHVjNzQwIFx1YjljOFx1YzZiMFx1YzJhNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVhZGY4XHViOWJjXHVjNzQ0IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNWM2XHVhY2UwIFx1ZDBhNFx1YmNmNFx1YjRkY1x1Yjg1YyBcdWJhODVcdWI4MzlcdWM1YjRcdWI5N2MgXHVjNzg1XHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZTk0XHViYzg0XHVjMmE0XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgKDAsIDApXHVjNzc0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCB4XHViODVjIFx1ZDU4OVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODhjXHVkNDVjXHViMjk0IHlcdWI4NWMgXHVjNWY0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVhZGRjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVhZGY4XHViOWJjXHVkMzEwIFx1YmE4NVx1YjgzOVx1YzViNFx1YjI5NCBQQUlOVCBjIHgxIHkxIHgyIHkyXHVjNzc0XHViMmU0LiBcdWM3NzQgXHViYTg1XHViODM5XHVjNWI0XHViMjk0IFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjY2I0XHVjMmE0XHVkMzEwIFx1ZDMyOFx1ZDEzNFx1YzczY1x1Yjg1YyBcdWNlNjBcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBjXHViMjk0IFx1YzBjOVx1Y2U2MFx1ZDU2MCBcdWMwYzlcdWMwYzFcdWM3NzRcdWFjZTAsICh4MSwgeTEpLCAoeDIsIHkyKVx1YjI5NCBcdWMwYzlcdWNlNjBcdWQ1NjAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3MDRcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDAgXHViYTg1XHViODM5XHVjNWI0XHVjNWQwXHVjMTFjIFx1YWNlMFx1Yjk3OCBcdWMwYzlcdWMwYzEgY1x1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMCBcdWNlNzhcdWM3NTggXHVjMGM5XHVjNzQwIFx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWQzMjhcdWQxMzRcdWM1ZDAgXHVjNzU4XHVkNTc0XHVjMTFjIFx1YWNiMFx1YzgxNVx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjMGM5XHVjZTYwXHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWNlNzhcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzQwIFx1YzZkMFx1Yjc5OCBcdWMwYzlcdWMwYzFcdWM3NDQgXHVhZGY4XHViMzAwXHViODVjIFx1YzcyMFx1YzljMFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWQ3NzBcdWMwYzkgXHVjZTk0XHViYzg0XHVjMmE0XHVjNWQwIFx1YmU2OFx1YWMwNCBcdWNjYjRcdWMyYTRcdWQzMTAgXHVkMzI4XHVkMTM0XHVjNzQ0IFx1Y2U2MFx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhaW50LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4MHB4OyB3aWR0aDoyMzNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YmNcdWQzMTBcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMwMFx1YzljMCBcdWJhODVcdWI4MzlcdWM1YjRcdWFjMDAgXHViMzU0IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOFx1YjI5NCBTQVZFXHViODVjIFx1ZDYwNFx1YzdhYyBcdWNlOTRcdWJjODRcdWMyYTRcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0IFx1YmE4NVx1YjgzOVx1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJhODVcdWI4MzlcdWM3NDAgTE9BRCB4XHViODVjIHhcdWJjODhcdWM5ZjggXHVjODAwXHVjN2E1XHVkNTVjIFx1Y2U5NFx1YmM4NFx1YzJhNFx1Yjk3YyBcdWJkODhcdWI3ZWNcdWM2MjRcdWIyOTQgXHViYTg1XHViODM5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWI4ZThcdWM4ODVcdWM3N2MgXHVhZGY4XHViOWJjXHVjNzQ0IFx1YWRmOFx1YjlhY1x1YjM1OCBcdWIzZDlcdWFkZGNcdWIyOTQgXHVjMmU0XHVjMjE4XHViODVjIFx1YzgwMFx1YzdhNVx1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM4ODVcdWI4Y2NcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzc0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODAwXHVjN2E1XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViM2Q5XHVhZGRjXHVhYzAwIFx1Yzc4NVx1YjgyNVx1ZDU1YyBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhYzAxIFx1Y2U3OFx1YzVkMCBcdWMwYzlcdWNlNjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzBjOVx1YzBjMVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxICZsZTsgTiAmbGU7IDEwMDApLCBLKDIgJmxlOyBLICZsZTsgMTAwLDAwMCksIE0oMSAmbGU7IE0gJmxlOyAxMDAsMDAwLCBNXHVjNzQwIFx1YmE4NVx1YjgzOVx1Yzc1OCBcdWFjMWNcdWMyMTgpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHVjMTM4IFx1YWMwMFx1YzljMCBcdWJhODVcdWI4MzlcdWM1YjRcdWM5MTEgXHVkNTU4XHViMDk4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNjJjXHViYzE0XHViOTc0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJhODVcdWI4MzlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Tlx1YWMxYyBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0xJS0EiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyBqdXN0IGluc3RhbGxlZCBhIGJyYW5kIG5ldyBkcmF3aW5nIHByb2dyYW0uIFRoZSBwcm9ncmFtIHN1cHBvcnRzIEsgZGlmZmVyZW50IGNvbG91cnMsIGRlbm90ZWQgYnkgaW50ZWdlcnMgZnJvbSAxIHRvIEsuIEFsbCBkcmF3aW5nIGlzIHBlcmZvcm1lZCBvbiBhIGNhbnZhcyB3aXRoIGRpbWVuc2lvbnMgTiZ0aW1lcztOLiBJbiB0aGUgYmVnaW5uaW5nLCBhbGwgY2VsbHMgYXJlIHdoaXRlIChkZW5vdGVkIGJ5IDEpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdXBwZXIgbGVmdCBjZWxsIG9mIHRoZSBjYW52YXMgaGFzIGNvb3JkaW5hdGVzICgwLCAwKS4gVGhlIGZpcnN0IGNvb3JkaW5hdGUsIHgsIGluY3JlYXNlcyBpdGVyYXRpbmcgb3ZlciByb3dzLCBhbmQgdGhlIHNlY29uZCwgeSwgaW5jcmVhc2VzIGl0ZXJhdGluZyBvdmVyIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvJnJzcXVvO3MgZmF2b3VyaXRlIHBhc3RpbWUgaXMgZHJhd2luZyByZWN0YW5ndWxhciBjaGVja2VyYm9hcmQgcGF0dGVybnMgdXNpbmcgdGhlIGNvbW1hbmQgUEFJTlQgYyB4MSB5MSB4MiB5Miwgd2hlcmUgYyBkZW5vdGVzIHRoZSBjaG9zZW4gY29sb3VyLCBhbmQgKHgxLCB5MSkgYW5kICh4MiwgeTIpIGFyZSBjb29yZGluYXRlcyBvZiB0aGUgdXBwZXIgbGVmdCBhbmQgbG93ZXIgcmlnaHQgY2VsbHMsIHJlc3BlY3RpdmVseSwgb2YgdGhlIHJlY3RhbmdsZSBiZWluZyBwYWludGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdXBwZXIgbGVmdCBjZWxsIG9mIHRoZSByZWN0YW5nbGUgd2lsbCBiZSBwYWludGVkIGluIHRoZSBjaG9zZW4gY29sb3VyLCB3aGlsZSB0aGUgcmVzdCBhcmUgZGV0ZXJtaW5lZCBieSB0aGUgY2hlY2tlcmJvYXJkIHBhdHRlcm4uIENlbGxzIHRoYXQgYXJlIG5vdCBwYWludGVkIG92ZXIgYnkgdGhlIGNob3NlbiBjb2xvdXIgd2lsbCByZXRhaW4gdGhlaXIgcHJldmlvdXMgY29sb3VyLiBGb3IgZXhhbXBsZSwgYSB3aGl0ZSBjYW52YXMgcGFpbnRlZCBvdmVyIGJ5IGEgcmVkIGNoZWNrZXJib2FyZCBwYXR0ZXJuIHdpbGwgbG9vayBsaWtlIHRoaXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGFpbnQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgwcHg7IHdpZHRoOjIzM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1pcmtvIGhhcyByZWNlbnRseSBkaXNjb3ZlcmVkIHR3byBhZGRpdGlvbmFsIGNvbW1hbmRzLiBIZSBjYW4gc2F2ZSBoaXMgcGFpbnRpbmcgYXQgYW55IHRpbWUgdXNpbmcgdGhlIGNyZWF0aXZlbHkgbmFtZWQgY29tbWFuZCBTQVZFLCBhbmQgbG9hZCBpdCBhZ2FpbiBsYXRlciB1c2luZyB0aGUgY29tbWFuZCBMT0FEIHgsIHdoZXJlIHggaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgb3JkaW5hbCBudW1iZXIgb2YgdGhlIHNhdmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIHRoZSBwcm9ncmFtIGhhcyBjcmFzaGVkIGFuZCBNaXJrbyZyc3F1bztzIHBhaW50aW5nIGlzIGxvc3QgZm9yZXZlci4gTHVja2lseSwgTWlya28gaGFzIHNhdmVkIGEgbG9nIG9mIGFsbCB1c2VkIGNvbW1hbmRzLiBDYW4geW91IGhlbHAgTWlya28gYnkgcmVjb25zdHJ1Y3RpbmcgdGhlIGxvc3QgcGFpbnRpbmc/Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMSAmbGU7IE4gJmxlOyAxMDAwKSwgSyAoMiAmbGU7IEsgJmxlOyAxMDAgMDAwKSwgYW5kIE0gKDEgJmxlOyBNICZsZTsgMTAwIDAwMCwgTSBpcyB0aGUgbnVtYmVyIG9mIGNvbW1hbmRzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgb25lIG9mIHRoZSB0aHJlZSBkZXNjcmliZWQgY29tbWFuZHMuIElucHV0IHdpbGwgbm90IGNvbnRhaW4gYW55IGlsbGVnYWwgY29tbWFuZHMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG11c3QgY29uc2lzdCBvZiBOIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgTiBpbnRlZ2VycyByZXByZXNlbnRpbmcgdGhlIGNvbG91cnMgb2YgY2VsbHMgaW4gdGhlIGNvcnJlc3BvbmRpbmcgcm93IG9mIHRoZSBwYWludGluZy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #5 6번

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