시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2260106482148.096%

문제

상근이는 건강을 위해 산책을 하려고 한다.

상근이가 사는 마을은 아래 그림과 같이 가로 방향 도로가 (H+1)개, 세로 방향 도로가 (W+1)개가 바둑판 모양으로 배치되어 있다. 상근이네 집은 가장 왼쪽 위 교차로에 있으며, 이곳에서 산책을 시작한다.

(a,b)는 위쪽에서 a번째, 왼쪽에서 b번째에 있는 교차로이다. 예를 들어, 상근이네 집은 교차로 (1,1)에 있다.

상근이는 산책 경로가 매일 달라야 질리지 않고 산책을 할 수 있다고 생각한다. 따라서, (1,1)에서 (H,W)까지 H × W개 교차로에 오른쪽을 뜻하는 오 또는 아래를 뜻하는 아를 쓰고, 다음과 같은 규칙에 따라서 산책을 하기로 했다.

교차로에 쓰여 있는 문자가 오라면, 이 문자를 지우고 아를 쓴다. 그 다음에 오른쪽으로 진행한다. 만약, 교차로에 쓰여 있는 문자가 아라면, 이 문자를 지우고 오를 쓴뒤, 아래로 진행한다.

이렇게 산책을 하다가 가장 오른쪽이나 아래쪽 도로에 도착하면 산책을 종료한다.

상근이는 이런 방법으로 산책을 계속 한다면, N번째 산책 경로가 어떻게 될지 궁금해졌다. H, W와 각 교차로에 써놓은 글자가 주어졌을 때, N번째 산책 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107)

둘째 줄부터 H개 줄에는 W개 정수가 주어진다. 이 정수는 상근이가 교차로에 써 놓은 문자의 정보이다. 0은 아래쪽을 의미하는 '아', 1은 오른쪽을 의미하는 '오'이다.

출력

N번째 산책에서 산책을 종료하는 교차로가 (i,j)라고 할 때, i와 j를 공백으로 구분하여 출력한다.

예제 입력 1

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

예제 출력 1

1 5

힌트

W3sicHJvYmxlbV9pZCI6IjU1NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYjBcdWNjNDUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjNzRcdWFjMTVcdWM3NDQgXHVjNzA0XHVkNTc0IFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMGFjXHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc0MCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjMDBcdWI4NWMgXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1Y1x1YWMwMCAoSCsxKVx1YWMxYywgXHVjMTM4XHViODVjIFx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWFjMDAgKFcrMSlcdWFjMWNcdWFjMDAgXHViYzE0XHViNDUxXHVkMzEwIFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjOWQxXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzVkMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc3NFx1YWNmM1x1YzVkMFx1YzExYyBcdWMwYjBcdWNjNDVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4oYSxiKVx1YjI5NCBcdWM3MDRcdWNhYmRcdWM1ZDBcdWMxMWMgYVx1YmM4OFx1YzlmOCwgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIGJcdWJjODhcdWM5ZjhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YzlkMVx1Yzc0MCBcdWFkNTBcdWNjMjhcdWI4NWMgKDEsMSlcdWM1ZDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGsucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI2cHg7IHdpZHRoOjM1MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMwYjBcdWNjNDUgXHVhY2JkXHViODVjXHVhYzAwIFx1YjllNFx1Yzc3YyBcdWIyZWNcdWI3N2NcdWM1N2MgXHVjOWM4XHViOWFjXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWMwYjBcdWNjNDVcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsICgxLDEpXHVjNWQwXHVjMTFjIChILFcpXHVhZTRjXHVjOWMwIEggJnRpbWVzOyBXXHVhYzFjIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzVkMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHViNzNiXHVkNTU4XHViMjk0IFx1YzYyNCBcdWI2MTBcdWIyOTQgXHVjNTQ0XHViNzk4XHViOTdjIFx1YjczYlx1ZDU1OFx1YjI5NCBcdWM1NDRcdWI5N2MgXHVjNGYwXHVhY2UwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM2MjRcdWI3N2NcdWJhNzQsIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjOWMwXHVjNmIwXHVhY2UwIFx1YzU0NFx1Yjk3YyBcdWM0ZjRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFkNTBcdWNjMjhcdWI4NWNcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNTQ0XHViNzdjXHViYTc0LCBcdWM3NzQgXHViYjM4XHVjNzkwXHViOTdjIFx1YzljMFx1YzZiMFx1YWNlMCBcdWM2MjRcdWI5N2MgXHVjNGY0XHViNGE0LCBcdWM1NDRcdWI3OThcdWI4NWMgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1ZDU1OFx1YjJlNFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzc0XHViMDk4IFx1YzU0NFx1Yjc5OFx1Y2FiZCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViYTc0IFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWI3ZjAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWFjYzRcdWMxOGQgXHVkNTVjXHViMmU0XHViYTc0LCBOXHViYzg4XHVjOWY4IFx1YzBiMFx1Y2M0NSBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNWI0XHViNWJiXHVhYzhjIFx1YjQyMFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIEgsIFdcdWM2NDAgXHVhYzAxIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzVkMCBcdWMzNjhcdWIxOTNcdWM3NDAgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE5cdWJjODhcdWM5ZjggXHVjMGIwXHVjYzQ1IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgSCwgVywgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgSCxXICZsZTsgMTAwMCwgMSAmbGU7IE4gJmxlOyAxMDxzdXA+NzxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgSFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgV1x1YWMxYyBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjODE1XHVjMjE4XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFkNTBcdWNjMjhcdWI4NWNcdWM1ZDAgXHVjMzY4IFx1YjE5M1x1Yzc0MCBcdWJiMzhcdWM3OTBcdWM3NTggXHVjODE1XHViY2Y0XHVjNzc0XHViMmU0LiAwXHVjNzQwIFx1YzU0NFx1Yjc5OFx1Y2FiZFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgJiMzOTtcdWM1NDQmIzM5OywgMVx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0ICYjMzk7XHVjNjI0JiMzOTtcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Tlx1YmM4OFx1YzlmOCBcdWMwYjBcdWNjNDVcdWM1ZDBcdWMxMWMgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1OFx1YjI5NCBcdWFkNTBcdWNjMjhcdWI4NWNcdWFjMDAgKGksailcdWI3N2NcdWFjZTAgXHVkNTYwIFx1YjU0YywgaVx1YzY0MCBqXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGtwYXRoLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2M3B4OyB3aWR0aDo2NDRweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTU3MyIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1NjU2M1x1NmI2OSIsImRlc2NyaXB0aW9uIjoiPHA+Sk9JXHU3NTNhXHUzMDZiXHU0ZjRmXHUzMDgwXHU1OTJhXHU5MGNlXHU1NDFiXHUzMDZmXHVmZjBjXHUzMDQyXHUzMDhiXHU2NWU1XHVmZjBjXHU1MDY1XHU1ZWI3XHU1ODk3XHU5MDMyXHUzMDZlXHUzMDVmXHUzMDgxXHUzMDZiXHU2NTYzXHU2YjY5XHUzMDkyXHU2NWU1XHU4YWIyXHUzMDZiXHUzMDU3XHUzMDg4XHUzMDQ2XHUzMDY4XHU2MDFkXHUzMDQ0XHU3YWNiXHUzMDYzXHUzMDVmXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTkyYVx1OTBjZVx1NTQxYlx1MzA2ZVx1NGY0Zlx1MzA4MCBKT0kgXHU3NTNhXHUzMDZiXHUzMDZmXHVmZjBjXHU1NmYzXHUzMDZlXHUzMDg4XHUzMDQ2XHUzMDZiXHVmZjBjXHU2NzcxXHU4OTdmXHU2NWI5XHU1NDExXHUzMDZiXHU4ZDcwXHUzMDhiIChIICsgMSkgXHU2NzJjXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDY4XHVmZjBjXHU1MzU3XHU1MzE3XHU2NWI5XHU1NDExXHUzMDZiXHU4ZDcwXHUzMDhiIChXICsgMSkgXHU2NzJjXHUzMDZlXHU5MDUzXHU4ZGVmXHUzMDRjXHU3ODgxXHU3NmU0XHU3NmVlXHU3MmI2XHUzMDZiXHU5MDFhXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU1OTJhXHU5MGNlXHU1NDFiXHUzMDZlXHU1YmI2XHUzMDZmXHUzMDgyXHUzMDYzXHUzMDY4XHUzMDgyXHU1MzE3XHU4OTdmXHUzMDZlXHU0ZWE0XHU1ZGVlXHU3MGI5XHUzMDZiXHUzMDQyXHUzMDhhXHVmZjBjXHUzMDUzXHUzMDUzXHUzMDRiXHUzMDg5XHU2NTYzXHU2YjY5XHUzMDkyXHU5NThiXHU1OWNiXHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NGVlNVx1OTY0ZFx1ZmYwY1x1NTMxN1x1MzA0Ylx1MzA4OSBhIFx1NzU2YVx1NzZlZVx1ZmYwY1x1ODk3Zlx1MzA0Ylx1MzA4OSBiIFx1NzU2YVx1NzZlZVx1MzA2ZVx1NGVhNFx1NWRlZVx1NzBiOVx1MzA5MiAoYSwgYikgXHUzMDY3XHU4ODY4XHUzMDU5XHVmZjBlXHUzMDVmXHUzMDY4XHUzMDQ4XHUzMDcwXHVmZjBjXHU1OTJhXHU5MGNlXHU1NDFiXHUzMDZlXHU1YmI2XHUzMDRjXHUzMDQyXHUzMDhiXHU0ZWE0XHU1ZGVlXHU3MGI5XHUzMDZmICgxLCAxKSBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9jMzY5YmNiNi1jYzU0LTRmMzctOGZjMC1mYjA5NzlkYWM5NDhcLy1cL2Nyb3BcLzY5Mng0MzlcLzAsM1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzQ2cHg7IGhlaWdodDogMjIwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlx1NTZmMzogSk9JIFx1NzUzYVx1MzA2ZVx1NTZmMyAoSCA9IDMsIFcgPSA0IFx1MzA2ZVx1NTgzNFx1NTQwOClcdWZmMGVcdTU2ZjNcdTMwNmVcdTRlMGFcdTMwNGNcdTUzMTdcdWZmMGNcdTVkZTZcdTMwNGNcdTg5N2ZcdTMwNmJcdTViZmVcdTVmZGNcdTMwNTlcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1OTJhXHU5MGNlXHU1NDFiXHUzMDZmXHVmZjBjXHU2NTYzXHU2YjY5XHUzMDZlXHUzMGViXHUzMGZjXHUzMGM4XHUzMDRjXHU2NWU1XHUzMDA1XHU5MDU1XHUzMDYzXHUzMDVmXHUzMDdiXHUzMDQ2XHUzMDRjXHU5NzYyXHU3NjdkXHUzMDQ0XHUzMDY4XHU4MDAzXHUzMDQ4XHUzMDVmXHUzMDZlXHUzMDY3XHVmZjBjKDEsIDEpXHUzMDRiXHUzMDg5KEgsIFcpXHUzMDdlXHUzMDY3XHUzMDZlIEggJnRpbWVzOyBXIFx1NTAwYlx1MzA2ZVx1NGVhNFx1NWRlZVx1NzBiOVx1MzA2Ylx1ZmYwY1x1MzAwY1x1Njc3MVx1MzAwZFx1MzA3ZVx1MzA1Zlx1MzA2Zlx1MzAwY1x1NTM1N1x1MzAwZFx1MzA2ZVx1NjU4N1x1NWI1N1x1MzA5Mlx1NjZmOFx1MzA0ZFx1ZmYwY1x1NmIyMVx1MzA2ZVx1MzA4OFx1MzA0Nlx1MzA2YVx1MzBlYlx1MzBmY1x1MzBlYlx1MzA2Ylx1NWY5M1x1MzA2M1x1MzA2Nlx1NmJjZVx1NjVlNVx1NjU2M1x1NmI2OVx1MzA5Mlx1ODg0Y1x1MzA0Nlx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA1N1x1MzA1Zlx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1NjU4N1x1NWI1N1x1MzA2ZVx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA1Zlx1NGVhNFx1NWRlZVx1NzBiOVx1MzA2Ylx1MzA0NFx1MzA4Ylx1NTgzNFx1NTQwOFx1ZmYwY1x1MzA1ZFx1MzA2ZVx1NGVhNFx1NWRlZVx1NzBiOVx1MzA2Ylx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1NjU4N1x1NWI1N1x1MzA0Y1x1MzAwY1x1Njc3MVx1MzAwZFx1MzA2YVx1MzA4OVx1MzAwY1x1NTM1N1x1MzAwZFx1MzA2Ylx1ZmYwY1x1MzAwY1x1NTM1N1x1MzAwZFx1MzA2YVx1MzA4OVx1MzAwY1x1Njc3MVx1MzAwZFx1MzA2Ylx1NjU4N1x1NWI1N1x1MzA5Mlx1NjZmOFx1MzA0ZFx1NjNkYlx1MzA0OFx1ZmYwY1x1MzA4Mlx1MzA2OFx1MzA4Mlx1MzA2OFx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA1Zlx1NjU4N1x1NWI1N1x1MzA2ZVx1NjViOVx1ODlkMlx1MzA2Ylx1MzA0Mlx1MzA4Ylx1NmIyMVx1MzA2ZVx1NGVhNFx1NWRlZVx1NzBiOVx1MzA3ZVx1MzA2N1x1OTAzMlx1MzA4MFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTMwODJcdTMwNjNcdTMwNjhcdTMwODJcdTY3NzFcdTMwODRcdTMwODJcdTMwNjNcdTMwNjhcdTMwODJcdTUzNTdcdTMwNmVcdTkwNTNcdThkZWZcdTMwNmJcdTUyMzBcdTkwNTRcdTMwNTdcdTMwNWZcdTMwODlcdTY1NjNcdTZiNjlcdTMwOTJcdTdkNDJcdTRlODZcdTMwNTlcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdTMwNTNcdTMwNmVcdThhMDhcdTc1M2JcdTMwOTJcdTgwMDNcdTMwNDhcdTMwNWZcdTVmOGNcdWZmMGNcdTU5MmFcdTkwY2VcdTU0MWJcdTMwNmZcdWZmMGNcdTVjMDZcdTY3NjVcdTMwNmVcdTY1NjNcdTZiNjlcdTMwNjdcdTgxZWFcdTUyMDZcdTMwNGNcdTMwNjlcdTMwNmVcdTMwODhcdTMwNDZcdTMwNmFcdTMwZWJcdTMwZmNcdTMwYzhcdTMwOTJcdTMwNWZcdTMwNjlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNmFcdTMwOGJcdTMwNmVcdTMwNGJcdTMwNGNcdTZjMTdcdTMwNmJcdTMwNmFcdTMwNjNcdTMwNWZcdWZmMGVcdTU5MmFcdTkwY2VcdTU0MWJcdTMwNmVcdTMwNWZcdTMwODFcdTMwNmJcdWZmMGNcdTU5MmFcdTkwY2VcdTU0MWJcdTMwNmUgTiBcdTU2ZGVcdTc2ZWVcdTMwNmVcdTY1NjNcdTZiNjlcdTMwNmVcdTMwZWJcdTMwZmNcdTMwYzhcdTMwOTJcdTRlODhcdTZlMmNcdTMwNTlcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjFcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGMzXHUzMDY0XHUzMDZlXHU2YjYzXHU2NTc0XHU2NTcwXHUzMDRjXHU3YTdhXHU3NjdkXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY3XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDg5XHUzMDZmXHVmZjBjXHU1NTRmXHU5ODRjXHU2NTg3XHU0ZTJkXHUzMDZlM1x1MzA2NFx1MzA2ZVx1NjU3MFx1NTAyNCBILCBXLCBOIFx1MzA2ZVx1NTAyNFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZUgsIFcsIE4gXHUzMDZmXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHVmZjBjMSAmbGU7IEggJmxlOyAxMDAwLCAxICZsZTsgVyAmbGU7IDEwMDAsIDEgNU4gJmxlOyAxMDAwMDAwMCA9IDEwPHN1cD43PFwvc3VwPiBcdTMwOTJcdTMwN2ZcdTMwNWZcdTMwNTlcdWZmMGUyIFx1ODg0Y1x1NzZlZVx1MzA0Ylx1MzA4OSBIICsgMSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGNcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGMgVyBcdTUwMGJcdTMwNmVcdTY1NzRcdTY1NzBcdTMwNGNcdTdhN2FcdTc2N2RcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjdcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmZcdWZmMGNcdTU5MmFcdTkwY2VcdTU0MWJcdTMwNGNcdTY3MDBcdTUyMWRcdTMwNmJcdTRlYTRcdTVkZWVcdTcwYjlcdTMwNmJcdTY2ZjhcdTMwNDRcdTMwNWZcdTY1ODdcdTViNTdcdTMwNmVcdTYwYzVcdTU4MzFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVpICsgMSBcdTg4NGNcdTc2ZWVcdTMwNmUgaiBcdTc1NmFcdTc2ZWVcdTMwNmVcdTY1NzRcdTY1NzBcdTMwNGMgMCBcdTMwNmFcdTMwODlcdWZmMGNcdTRlYTRcdTVkZWVcdTcwYjkgKGksIGopIFx1MzA2Ylx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA1Zlx1NjU4N1x1NWI1N1x1MzA0Y1x1MzAwY1x1NTM1N1x1MzAwZFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ZmYwYzEgXHUzMDZhXHUzMDg5XHVmZjBjXHU0ZWE0XHU1ZGVlXHU3MGI5IChpLCBqKSBcdTMwNmJcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNWZcdTY1ODdcdTViNTdcdTMwNGNcdTMwMGNcdTY3NzFcdTMwMGRcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OIFx1NTZkZVx1NzZlZVx1MzA2ZVx1NjU2M1x1NmI2OVx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1NTkyYVx1OTBjZVx1NTQxYlx1MzA0Y1x1NjU2M1x1NmI2OVx1MzA5Mlx1N2Q0Mlx1NGU4Nlx1MzA1OVx1MzA4Ylx1NGVhNFx1NWRlZVx1NzBiOVx1MzA0YyAoaSwgaikgXHUzMDZlXHUzMDY4XHUzMDRkXHVmZjBjaSBcdTMwNjggaiBcdTMwOTJcdTMwNTNcdTMwNmVcdTk4MDZcdTMwNmJcdTdhN2FcdTc2N2RcdTMwNjdcdTUzM2FcdTUyMDdcdTMwNjNcdTMwNjZcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9lNjU1YjA4MC1mMWM2LTRhZWYtYTI4My05MTE2ZWExMzE1YTBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDYwNHB4OyBoZWlnaHQ6IDE0NHB4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiSmFwYW5lc2UifV0=

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2008/2009 4번