시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 21 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+XHViM2Q5XHVhZGRjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVhZGY4XHViOWJjXHVkMzEwIFx1YmE4NVx1YjgzOVx1YzViNFx1YjI5NCBQQUlOVCBjIHgxIHkxIHgyIHkyXHVjNzc0XHViMmU0LiBcdWM3NzQgXHViYTg1XHViODM5XHVjNWI0XHViMjk0IFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjY2I0XHVjMmE0XHVkMzEwIFx1ZDMyOFx1ZDEzNFx1YzczY1x1Yjg1YyBcdWNlNjBcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBjXHViMjk0IFx1YzBjOVx1Y2U2MFx1ZDU2MCBcdWMwYzlcdWMwYzFcdWM3NzRcdWFjZTAsICh4MSwgeTEpLCAoeDIsIHkyKVx1YjI5NCBcdWMwYzlcdWNlNjBcdWQ1NjAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3MDRcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDAgXHViYTg1XHViODM5XHVjNWI0XHVjNWQwXHVjMTFjIFx1YWNlMFx1Yjk3OCBcdWMwYzlcdWMwYzEgY1x1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMCBcdWNlNzhcdWM3NTggXHVjMGM5XHVjNzQwIFx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWQzMjhcdWQxMzRcdWM1ZDAgXHVjNzU4XHVkNTc0XHVjMTFjIFx1YWNiMFx1YzgxNVx1YjQxY1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWMwYzlcdWNlNjBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDAgXHVjNmQwXHViNzk4IFx1YzBjOVx1YzBjMVx1Yzc0NCBcdWFkZjhcdWIzMDBcdWI4NWMgXHVjNzIwXHVjOWMwXHVkNTVjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDc3MFx1YzBjOSBcdWNlOTRcdWJjODRcdWMyYTRcdWM1ZDAgXHViZTY4XHVhYzA0IFx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWQzMjhcdWQxMzRcdWM3NDQgXHVjZTYwXHVkNTg4XHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGFpbnQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgwcHg7IHdpZHRoOjIzM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliY1x1ZDMxMFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YmE4NVx1YjgzOVx1YzViNFx1YWMwMCBcdWIzNTQgXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4XHViMjk0IFNBVkVcdWI4NWMgXHVkNjA0XHVjN2FjIFx1Y2U5NFx1YmM4NFx1YzJhNFx1Yjk3YyBcdWM4MDBcdWM3YTVcdWQ1NThcdWIyOTQgXHViYTg1XHViODM5XHVjNzc0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YmE4NVx1YjgzOVx1Yzc0MCBMT0FEIHhcdWI4NWMgeFx1YmM4OFx1YzlmOCBcdWM4MDBcdWM3YTVcdWQ1NWMgXHVjZTk0XHViYzg0XHVjMmE0XHViOTdjIFx1YmQ4OFx1YjdlY1x1YzYyNFx1YjI5NCBcdWJhODVcdWI4MzlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YjhlOFx1Yzg4NVx1Yzc3YyBcdWFkZjhcdWI5YmNcdWM3NDQgXHVhZGY4XHViOWFjXHViMzU4IFx1YjNkOVx1YWRkY1x1YjI5NCBcdWMyZTRcdWMyMThcdWI4NWMgXHVjODAwXHVjN2E1XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NzQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzBhY1x1YzZhOVx1Yzc5MFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHViYTg1XHViODM5XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4MDBcdWM3YTVcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIzZDlcdWFkZGNcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzBjOVx1Y2U2MFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMGM5XHVjMGMxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMTAwMCksIEsoMiAmbGU7IEsgJmxlOyAxMDAsMDAwKSwgTSgxICZsZTsgTSAmbGU7IDEwMCwwMDAsIE1cdWM3NDAgXHViYTg1XHViODM5XHVjNzU4IFx1YWMxY1x1YzIxOClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWMxMzggXHVhYzAwXHVjOWMwIFx1YmE4NVx1YjgzOVx1YzViNFx1YzkxMSBcdWQ1NThcdWIwOThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM2MmNcdWJjMTRcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmE4NVx1YjgzOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OXHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNMSUtBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMganVzdCBpbnN0YWxsZWQgYSBicmFuZCBuZXcgZHJhd2luZyBwcm9ncmFtLiBUaGUgcHJvZ3JhbSBzdXBwb3J0cyBLIGRpZmZlcmVudCBjb2xvdXJzLCBkZW5vdGVkIGJ5IGludGVnZXJzIGZyb20gMSB0byBLLiBBbGwgZHJhd2luZyBpcyBwZXJmb3JtZWQgb24gYSBjYW52YXMgd2l0aCBkaW1lbnNpb25zIE4mdGltZXM7Ti4gSW4gdGhlIGJlZ2lubmluZywgYWxsIGNlbGxzIGFyZSB3aGl0ZSAoZGVub3RlZCBieSAxKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHVwcGVyIGxlZnQgY2VsbCBvZiB0aGUgY2FudmFzIGhhcyBjb29yZGluYXRlcyAoMCwgMCkuIFRoZSBmaXJzdCBjb29yZGluYXRlLCB4LCBpbmNyZWFzZXMgaXRlcmF0aW5nIG92ZXIgcm93cywgYW5kIHRoZSBzZWNvbmQsIHksIGluY3JlYXNlcyBpdGVyYXRpbmcgb3ZlciBjb2x1bW5zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyZyc3F1bztzIGZhdm91cml0ZSBwYXN0aW1lIGlzIGRyYXdpbmcgcmVjdGFuZ3VsYXIgY2hlY2tlcmJvYXJkIHBhdHRlcm5zIHVzaW5nIHRoZSBjb21tYW5kIFBBSU5UIGMgeDEgeTEgeDIgeTIsIHdoZXJlIGMgZGVub3RlcyB0aGUgY2hvc2VuIGNvbG91ciwgYW5kICh4MSwgeTEpIGFuZCAoeDIsIHkyKSBhcmUgY29vcmRpbmF0ZXMgb2YgdGhlIHVwcGVyIGxlZnQgYW5kIGxvd2VyIHJpZ2h0IGNlbGxzLCByZXNwZWN0aXZlbHksIG9mIHRoZSByZWN0YW5nbGUgYmVpbmcgcGFpbnRlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHVwcGVyIGxlZnQgY2VsbCBvZiB0aGUgcmVjdGFuZ2xlIHdpbGwgYmUgcGFpbnRlZCBpbiB0aGUgY2hvc2VuIGNvbG91ciwgd2hpbGUgdGhlIHJlc3QgYXJlIGRldGVybWluZWQgYnkgdGhlIGNoZWNrZXJib2FyZCBwYXR0ZXJuLiBDZWxscyB0aGF0IGFyZSBub3QgcGFpbnRlZCBvdmVyIGJ5IHRoZSBjaG9zZW4gY29sb3VyIHdpbGwgcmV0YWluIHRoZWlyIHByZXZpb3VzIGNvbG91ci4gRm9yIGV4YW1wbGUsIGEgd2hpdGUgY2FudmFzIHBhaW50ZWQgb3ZlciBieSBhIHJlZCBjaGVja2VyYm9hcmQgcGF0dGVybiB3aWxsIGxvb2sgbGlrZSB0aGlzOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhaW50LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4MHB4OyB3aWR0aDoyMzNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5NaXJrbyBoYXMgcmVjZW50bHkgZGlzY292ZXJlZCB0d28gYWRkaXRpb25hbCBjb21tYW5kcy4gSGUgY2FuIHNhdmUgaGlzIHBhaW50aW5nIGF0IGFueSB0aW1lIHVzaW5nIHRoZSBjcmVhdGl2ZWx5IG5hbWVkIGNvbW1hbmQgU0FWRSwgYW5kIGxvYWQgaXQgYWdhaW4gbGF0ZXIgdXNpbmcgdGhlIGNvbW1hbmQgTE9BRCB4LCB3aGVyZSB4IGlzIGEgcG9zaXRpdmUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG9yZGluYWwgbnVtYmVyIG9mIHRoZSBzYXZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCB0aGUgcHJvZ3JhbSBoYXMgY3Jhc2hlZCBhbmQgTWlya28mcnNxdW87cyBwYWludGluZyBpcyBsb3N0IGZvcmV2ZXIuIEx1Y2tpbHksIE1pcmtvIGhhcyBzYXZlZCBhIGxvZyBvZiBhbGwgdXNlZCBjb21tYW5kcy4gQ2FuIHlvdSBoZWxwIE1pcmtvIGJ5IHJlY29uc3RydWN0aW5nIHRoZSBsb3N0IHBhaW50aW5nPyZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgcG9zaXRpdmUgaW50ZWdlcnMsIE4gKDEgJmxlOyBOICZsZTsgMTAwMCksIEsgKDIgJmxlOyBLICZsZTsgMTAwIDAwMCksIGFuZCBNICgxICZsZTsgTSAmbGU7IDEwMCAwMDAsIE0gaXMgdGhlIG51bWJlciBvZiBjb21tYW5kcykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIG9uZSBvZiB0aGUgdGhyZWUgZGVzY3JpYmVkIGNvbW1hbmRzLiBJbnB1dCB3aWxsIG5vdCBjb250YWluIGFueSBpbGxlZ2FsIGNvbW1hbmRzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBtdXN0IGNvbnNpc3Qgb2YgTiBsaW5lcywgZWFjaCBjb250YWluaW5nIE4gaW50ZWdlcnMgcmVwcmVzZW50aW5nIHRoZSBjb2xvdXJzIG9mIGNlbGxzIGluIHRoZSBjb3JyZXNwb25kaW5nIHJvdyBvZiB0aGUgcGFpbnRpbmcuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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