시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 83 20 17 28.814%

문제

주식회사 금고는 매우 안전한 금고를 만드는 회사이다. 금고사의 최신 금고는 빛을 이용한다. 직사각형 그리드에 거울을 적절히 넣고, 레이저를 발사해 감지기에 레이저가 감지되는지를 확인한다.

레이저는 그리드의 가장 윗 행의 왼쪽에서 발사된다. 레이저가 거울을 만난 경우에 레이저는 반사된다. 모든 거울은 45도 대각선 방향 (\ 또는 /)이다. 레이저가 가장 아랫 행의 오른쪽으로 빠져 나올 때(왼쪽 그림), 금고가 열린다. 그 외의 경우에는 알람이 울린다.

모든 금고에는 거울이 한 개씩 빠져있다. (오른쪽 그림) 사용자는 거울 한 개를 비어있는 칸에 넣는다. 올바른 사용자는 거울의 정확한 위치와 모양 (4행 3열, /)을 알고 있기 때문에, 금고를 안전하게 열 수 있다.

금고의 정보가 주어졌을 때, 금고가 안전한지 아닌지 구하는 프로그램을 작성하시오. 안전한 금고는 거울을 넣지 않았을 때 열리면 안되며, 금고를 열 수 있는 거울의 위치와 모양이 적어도 한 개는 존재한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고 각 테스트 케이스는 금고 하나를 나타낸다.

테스트 케이스의 첫째 줄에는 네정수 r, c, m, n이 주어진다. (1 ≤ r,c ≤ 1,000,000, 0 ≤ m,n ≤ 200,000) 금고는 r행 c열로 이루어져 있다.

다음 m개 줄에는 두 정수 ri와 ci (1 ≤ ri ≤ r, 1 ≤ ci ≤ c)가 주어지며, ri행 ci 열에 /모양의 거울이 있다는 뜻이다.

다음 n개 줄에도 \모양 거울의 정보가 주어지며, /모양 정보와 같은 방식으로 주어진다.

모든 m+n개의 위치는 서로 다르다. 

출력

각 테스트 케이스마다, 테스트 케이스 번호를 출력하고 다음을 출력한다.

  • 0 거울을 삽입하지 않고 금고를 열 수 있을때
  • k r c 거울을 넣지 않으면 금고가 열리지 않고, 금고를 열 수 있는 위치의 수가 k개, 그 중 가장 사전순으로 앞서는 위치가 (r, c)인 경우 (한 위치에 /와 \ 모양의 거울을 넣을 수 있는 경우에 위치 1개로 센다)
  • impossible 거울을 넣어도 금고를 열 수 없는 경우

예제 입력 1

5 6 1 4
2 3
1 2
2 5
4 2
5 5
100 100 0 2
1 77
100 77
100 100 0 0

예제 출력 1

Case 1: 2 4 3
Case 2: 0
Case 3: impossible

힌트

W3sicHJvYmxlbV9pZCI6IjQyMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMDhcdWFjZTAgXHVkNjhjXHVjMGFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4ZmNcdWMyZGRcdWQ2OGNcdWMwYWMgXHVhZTA4XHVhY2UwXHViMjk0IFx1YjllNFx1YzZiMCBcdWM1NDhcdWM4MDRcdWQ1NWMgXHVhZTA4XHVhY2UwXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ2OGNcdWMwYWNcdWM3NzRcdWIyZTQuIFx1YWUwOFx1YWNlMFx1YzBhY1x1Yzc1OCBcdWNkNWNcdWMyZTAgXHVhZTA4XHVhY2UwXHViMjk0IFx1YmU1Ylx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDAgXHVhYzcwXHVjNmI4XHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWIxMjNcdWFjZTAsIFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjk3YyBcdWJjMWNcdWMwYWNcdWQ1NzQgXHVhYzEwXHVjOWMwXHVhZTMwXHVjNWQwIFx1YjgwOFx1Yzc3NFx1YzgwMFx1YWMwMCBcdWFjMTBcdWM5YzBcdWI0MThcdWIyOTRcdWM5YzBcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21pcnJvLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3OHB4OyB3aWR0aDo2MDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI4MDhcdWM3NzRcdWM4MDBcdWIyOTQgXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM3MTcgXHVkNTg5XHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWJjMWNcdWMwYWNcdWI0MWNcdWIyZTQuIFx1YjgwOFx1Yzc3NFx1YzgwMFx1YWMwMCBcdWFjNzBcdWM2YjhcdWM3NDQgXHViOWNjXHViMDljIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWI4MDhcdWM3NzRcdWM4MDBcdWIyOTQgXHViYzE4XHVjMGFjXHViNDFjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhYzcwXHVjNmI4XHVjNzQwIDQ1XHViM2M0IFx1YjMwMFx1YWMwMVx1YzEyMCBcdWJjMjlcdWQ1YTUgKFxcIFx1YjYxMFx1YjI5NCBcLylcdWM3NzRcdWIyZTQuIFx1YjgwOFx1Yzc3NFx1YzgwMFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViN2FiIFx1ZDU4OVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHViZTYwXHVjODM4IFx1YjA5OFx1YzYyYyBcdWI1NGMoXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliYyksIFx1YWUwOFx1YWNlMFx1YWMwMCBcdWM1ZjRcdWI5YjBcdWIyZTQuIFx1YWRmOCBcdWM2NzhcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0Y1x1Yjc4Y1x1Yzc3NCBcdWM2YjhcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWFlMDhcdWFjZTBcdWM1ZDBcdWIyOTQgXHVhYzcwXHVjNmI4XHVjNzc0IFx1ZDU1YyBcdWFjMWNcdWM1MjkgXHViZTYwXHVjODM4XHVjNzg4XHViMmU0LiAoXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliYykgXHVjMGFjXHVjNmE5XHVjNzkwXHViMjk0IFx1YWM3MFx1YzZiOCBcdWQ1NWMgXHVhYzFjXHViOTdjIFx1YmU0NFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LiBcdWM2MmNcdWJjMTRcdWI5NzggXHVjMGFjXHVjNmE5XHVjNzkwXHViMjk0IFx1YWM3MFx1YzZiOFx1Yzc1OCBcdWM4MTVcdWQ2NTVcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YmFhOFx1YzU5MSAoNFx1ZDU4OSAzXHVjNWY0LCBcLylcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWUwOFx1YWNlMFx1Yjk3YyBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHVjNWY0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWUwOFx1YWNlMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZTA4XHVhY2UwXHVhYzAwIFx1YzU0OFx1YzgwNFx1ZDU1Y1x1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzU0OFx1YzgwNFx1ZDU1YyBcdWFlMDhcdWFjZTBcdWIyOTQgXHVhYzcwXHVjNmI4XHVjNzQ0IFx1YjEyM1x1YzljMCBcdWM1NGFcdWM1NThcdWM3NDQgXHViNTRjIFx1YzVmNFx1YjlhY1x1YmE3NCBcdWM1NDhcdWI0MThcdWJhNzAsIFx1YWUwOFx1YWNlMFx1Yjk3YyBcdWM1ZjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWM2YjhcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YmFhOFx1YzU5MVx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YWMxY1x1YjI5NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVhZTA4XHVhY2UwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxMjRcdWM4MTVcdWMyMTggciwgYywgbSwgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgcixjICZsZTsgMSwwMDAsMDAwLCAwICZsZTsgbSxuICZsZTsgMjAwLDAwMCkgXHVhZTA4XHVhY2UwXHViMjk0IHJcdWQ1ODkgY1x1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCByPHN1Yj5pPFwvc3ViPlx1YzY0MCBjPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IHI8c3ViPmk8XC9zdWI+ICZsZTsgciwgMSAmbGU7IGM8c3ViPmk8XC9zdWI+ICZsZTsgYylcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCByPHN1Yj5pPFwvc3ViPlx1ZDU4OSBjPHN1Yj5pPFwvc3ViPiBcdWM1ZjRcdWM1ZDAgXC9cdWJhYThcdWM1OTFcdWM3NTggXHVhYzcwXHVjNmI4XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjNjNCBcXFx1YmFhOFx1YzU5MSZuYnNwO1x1YWM3MFx1YzZiOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcL1x1YmFhOFx1YzU5MSBcdWM4MTVcdWJjZjRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBtK25cdWFjMWNcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCBcdWIyZTRcdWM3NGNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPjA8XC9jb2RlPiBcdWFjNzBcdWM2YjhcdWM3NDQgXHVjMGJkXHVjNzg1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFlMDhcdWFjZTBcdWI5N2MgXHVjNWY0IFx1YzIxOCBcdWM3ODhcdWM3NDRcdWI1NGM8XC9saT5cclxuXHQ8bGk+PGNvZGU+ayByIGM8XC9jb2RlPiBcdWFjNzBcdWM2YjhcdWM3NDQgXHViMTIzXHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWFlMDhcdWFjZTBcdWFjMDAgXHVjNWY0XHViOWFjXHVjOWMwIFx1YzU0YVx1YWNlMCwgXHVhZTA4XHVhY2UwXHViOTdjIFx1YzVmNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWMyMThcdWFjMDAga1x1YWMxYywgXHVhZGY4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWM3MDRcdWNlNThcdWFjMDAgKHIsIGMpXHVjNzc4IFx1YWNiZFx1YzZiMCAoXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzVkMCBcL1x1YzY0MCBcXCBcdWJhYThcdWM1OTFcdWM3NTggXHVhYzcwXHVjNmI4XHVjNzQ0IFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM3MDRcdWNlNTggMVx1YWMxY1x1Yjg1YyBcdWMxM2NcdWIyZTQpPFwvbGk+XHJcblx0PGxpPjxjb2RlPmltcG9zc2libGU8XC9jb2RlPiBcdWFjNzBcdWM2YjhcdWM3NDQgXHViMTIzXHVjNWI0XHViM2M0IFx1YWUwOFx1YWNlMFx1Yjk3YyBcdWM1ZjQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjA8XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQyMTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBIFNhZmUgQmV0IiwiZGVzY3JpcHRpb24iOiI8cD5TYWZlIEx0ZC4gaXMgYSBjb21wYW55IHRoYXQgbWFudWZhY3R1cmVzIGhpZ2gtcXVhbGl0eSBzYWZlcy4gSXRzIGxhdGVzdCBpbnZlbnRpb24gaXMgYW4gb3B0aWNhbCBjbG9zdXJlIG1lY2hhbmlzbSB0aGF0IHVzZXMgYSBsYXNlciBiZWFtIHBhc3NpbmcgdGhyb3VnaCBhIHJlY3Rhbmd1bGFyIGdyaWQgd2l0aCBzZXZlcmFsIG1pcnJvcnMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWlycm8ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTc4cHg7IHdpZHRoOjYwMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldoZW4gdGhlIGxhc2VyIGlzIGFjdGl2YXRlZCwgYSBiZWFtIGVudGVycyB0aGUgdG9wIHJvdyBvZiB0aGUgZ3JpZCBob3Jpem9udGFsbHkgZnJvbSB0aGUgbGVmdC4gVGhlIGJlYW0gaXMgcmVmbGVjdGVkIGJ5IGV2ZXJ5IG1pcnJvciB0aGF0IGl0IGhpdHMuIEVhY2ggbWlycm9yIGhhcyBhIDQ1IGRlZ3JlZSBkaWFnb25hbCBvcmllbnRhdGlvbiwgZWl0aGVyIFwvIG9yIFxcLiBJZiB0aGUgYmVhbSBleGl0cyB0aGUgYm90dG9tIHJvdyBvZiB0aGUgZ3JpZCBob3Jpem9udGFsbHkgdG8gdGhlIHJpZ2h0LCBpdCBpcyBkZXRlY3RlZCBhbmQgdGhlIHNhZmUgb3BlbnMgKHNlZSB0aGUgbGVmdCBzaWRlIG9mIHRoZSBcdWZiMDFndXJlIGFib3ZlKS4gT3RoZXJ3aXNlIHRoZSBzYWZlIHJlbWFpbnMgY2xvc2VkIGFuZCBhbiBhbGFybSBpcyByYWlzZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggc2FmZSBoYXMgYSBtaXNzaW5nIG1pcnJvciwgd2hpY2ggcHJldmVudHMgdGhlIGxhc2VyIGJlYW0gZnJvbSB0cmF2ZWxpbmcgc3VjY2Vzc2Z1bGx5IHRocm91Z2ggdGhlIGdyaWQgKHNlZSB0aGUgcmlnaHQgc2lkZSBvZiB0aGUgXHVmYjAxZ3VyZSBhYm92ZSkuIFRoZSBzYWZlIGhhcyBhIG1lY2hhbmlzbSB0aGF0IGVuYWJsZXMgdGhlIHVzZXIgdG8gZHJvcCBhIHNpbmdsZSBtaXJyb3IgaW50byBhbnkgZW1wdHkgZ3JpZCBjZWxsLiBBIGxlZ2l0aW1hdGUgdXNlciBrbm93cyB0aGUgY29ycmVjdCBwb3NpdGlvbiBhbmQgb3JpZW50YXRpb24gb2YgdGhlIG1pc3NpbmcgbWlycm9yIChcLyBpbiByb3cgNCBjb2x1bW4gMyBhYm92ZSkgYW5kIGNhbiB0aHVzIG9wZW4gdGhlIHNhZmUuIFdpdGhvdXQgdGhpcyBrbm93bGVkZ2UgdGhlIHVzZXIgaGFzIHRvIGd1ZXNzIGNvcnJlY3RseSwgd2hpY2ggY2FuIGJlIGRpZlx1ZmIwMWN1bHQgZm9yIHNhZmVzIHdpdGggbGFyZ2UgZ3JpZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgam9iIGlzIHRvIGRldGVybWluZSBpZiBwYXJ0aWN1bGFyIHNhZmVzIGFyZSBhY3R1YWxseSBzZWN1cmUuIEEgc2VjdXJlIHNhZmUgZG9lcyBub3Qgb3BlbiByaWdodCBhd2F5IHdpdGhvdXQgaW5zZXJ0aW5nIGEgbWlycm9yLCBhbmQgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIHZhbGlkIGxvY2F0aW9uIGFuZCBvcmllbnRhdGlvbiBmb3IgdGhlIG1pc3NpbmcgbWlycm9yLiBUaGVyZSBtYXkgaW5kZWVkIGJlIG11bHRpcGxlIHN1Y2ggbG9jYXRpb25zIGFuZCBvcmllbnRhdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBkZXNjcmliZXMgYSBzaW5nbGUgc2FmZSBhbmQgc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgZm91ciBpbnRlZ2VyIG51bWJlcnMgciwgYywgbSwgYW5kIG4gKDEgJmxlOyByLCBjICZsZTsgMSAwMDAgMDAwIGFuZCAwICZsZTsgbSwgbiAmbGU7IDIwMCAwMDApLiBUaGUgbWVjaGFuaXNtJnJzcXVvO3MgZ3JpZCBoYXMgciByb3dzIGFuZCBjIGNvbHVtbnMuIEVhY2ggb2YgdGhlIG5leHQgbSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlciBudW1iZXJzIHI8c3ViPmk8XC9zdWI+IGFuZCBjPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IHI8c3ViPmk8XC9zdWI+ICZsZTsgciBhbmQgMSAmbGU7IGM8c3ViPmk8XC9zdWI+ICZsZTsgYykgc3BlY2lmeWluZyB0aGF0IHRoZXJlIGlzIGEgXC8gbWlycm9yIGluIHJvdyByPHN1Yj5pPFwvc3ViPiBjb2x1bW4gYzxzdWI+aTxcL3N1Yj4uIFRoZSBmb2xsb3dpbmcgbiBsaW5lcyBzcGVjaWZ5IHRoZSBwb3NpdGlvbnMgb2YgdGhlIFxcIG1pcnJvcnMgaW4gdGhlIHNhbWUgd2F5LiBUaGUgbSArIG4gcG9zaXRpb25zIG9mIHRoZSBtaXJyb3JzIGFyZSBwYWlyd2lzZSBkaXN0aW5jdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgaXRzIGNhc2UgbnVtYmVyIGZvbGxvd2VkIGJ5OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPjA8XC9jb2RlPiBpZiB0aGUgc2FmZSBvcGVucyB3aXRob3V0IGluc2VydGluZyBhIG1pcnJvci48XC9saT5cclxuXHQ8bGk+PGNvZGU+ayByIGM8XC9jb2RlPiBpZiB0aGUgc2FmZSBkb2VzIG5vdCBvcGVuIHdpdGhvdXQgaW5zZXJ0aW5nIGEgbWlycm9yLCB0aGVyZSBhcmUgZXhhY3RseSBrIHBvc2l0aW9ucyB3aGVyZSBpbnNlcnRpbmcgYSBtaXJyb3Igb3BlbnMgdGhlIHNhZmUsIGFuZCAociwgYykgaXMgdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0IHN1Y2ggcm93LCBjb2x1bW4gcG9zaXRpb24uIEEgcG9zaXRpb24gd2hlcmUgYm90aCBhIFwvIGFuZCBhIFxcIG1pcnJvciBvcGVuIHRoZSBzYWZlIGNvdW50cyBqdXN0IG9uY2UuPFwvbGk+XHJcblx0PGxpPjxjb2RlPmltcG9zc2libGU8XC9jb2RlPiBpZiB0aGUgc2FmZSBjYW5ub3QgYmUgb3BlbmVkIHdpdGggb3Igd2l0aG91dCBpbnNlcnRpbmcgYSBtaXJyb3IuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > World Finals > 2012 World Finals I번