시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 198 74 54 42.857%

문제

인류는 선사시대부터 물체와 건물을 장식해왔다. 이러한 장식에서 가장 중요한 요소는 기하학문양이다. 우리는 일상생활 속에서 기하학문양을 손쉽게 찾아볼 수 있다.

유명한 계산 기하학 전문가 수환이는 기하학문양이 그리드와 다양한 서브 그리드 위에서 매우 정교하게 만들어졌다는 사실을 알게 되었다. 수환이는 최근에 기하학문양을 자동으로 만들어주는 연구 프로젝트를 시작했다.

수환이가 관심을 갖는 그리드는 직사각형 그리드와 원형 그리드이다. m × n 직사각형 그리드는 한 평면 위에 있는 정점과 간선이 직사각형을 이루는 그래프이다. 그래프의 각 행에 있는 정점의 수는 n개, 각 열에 있는 정점의 수는 m개이다. 그래프의 정점은 {vji : 0 ≤ i ≤ m-1, 0 ≤ j ≤ n-1} 으로, 간선은 {(vji, vqp) : |i - p| + |j - q| = 1} 으로 나타낼 수 있다. m × n 원형 그리드는 m × n 직사각형 그리드에 간선을 추가해 동그랗게 만든 그래프이다. 즉, 모든 0 ≤ i ≤ m-1에 대해서, (vn-1i, v0i)를 추가한 그래프이다. 2 × 6 직사각형 그리드와 원형 그리드는 아래 그림 1과 2에 나와있다.

많은 기하학문양은 그리드 상에서 스패닝 트리를 이루고 있다. 스패닝 트리는 사이클 없이 모두 연결된 그래프이며, 그래프의 모든 정점과 일부 간선으로 이루어져 있다. 수환이는 2 × n 그리드에서 만들 수 있는 서로 다른 스패닝 트리의 개수를 세보려고 한다. 그래프의 각 정점은 다른 정점과 모두 구분된다. 그림 2에 나와있는 두 스패닝 트리는 다른 경우로 세야 한다.

n이 주어졌을 때, 2 × n 직사각형 그리드와 2 × n 원형 그리드에서 만들 수 있는 스패닝 트리의 개수를 구하는 프로그램을 작성하시오.

그림 1. 2 × 6 직사각형 그리드와 스패닝 트리 한 개

그림 2. 2 × 6 원형 그리드와 서로 다른 스패닝 트리 두 개

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 하나 주어진다. (3 ≤ n ≤ 50,000)

출력

각 테스트 케이스마다 Rn을 10,007로 나눈 나머지와 Cn을 10,007로 나눈 나머지를 출력한다. Rn은 2 × n 직사각형 그리드에서 만들 수 있는 스패닝 트리의 개수, Cn은 2 × n 원형 그리드에서 만들 수 있는 스패닝 트리의 개수이다.

예제 입력 1

3
3
4
10

예제 출력 1

15 75
56 384
1211 9033
W3sicHJvYmxlbV9pZCI6Ijk0NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzBcdWQ1NThcdWQ1NTlcdWJiMzhcdWM1OTEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3OFx1Yjk1OFx1YjI5NCBcdWMxMjBcdWMwYWNcdWMyZGNcdWIzMDBcdWJkODBcdWQxMzAgXHViYjNjXHVjY2I0XHVjNjQwIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWM3YTVcdWMyZGRcdWQ1NzRcdWM2NTRcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM3YTVcdWMyZGRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWM2OTRcdWMxOGNcdWIyOTQgXHVhZTMwXHVkNTU4XHVkNTU5XHViYjM4XHVjNTkxXHVjNzc0XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzdjXHVjMGMxXHVjMGRkXHVkNjVjIFx1YzE4ZFx1YzVkMFx1YzExYyBcdWFlMzBcdWQ1NThcdWQ1NTlcdWJiMzhcdWM1OTFcdWM3NDQgXHVjMTkwXHVjMjdkXHVhYzhjIFx1Y2MzZVx1YzU0NFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWJhODVcdWQ1NWMgXHVhY2M0XHVjMGIwIFx1YWUzMFx1ZDU1OFx1ZDU1OSBcdWM4MDRcdWJiMzhcdWFjMDAgXHVjMjE4XHVkNjU4XHVjNzc0XHViMjk0IFx1YWUzMFx1ZDU1OFx1ZDU1OVx1YmIzOFx1YzU5MVx1Yzc3NCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM2NDAgXHViMmU0XHVjNTkxXHVkNTVjIFx1YzExY1x1YmUwYyBcdWFkZjhcdWI5YWNcdWI0ZGMgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YjllNFx1YzZiMCBcdWM4MTVcdWFkNTBcdWQ1NThcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHVjODRjXHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiZuYnNwO1x1YzIxOFx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWFkZmNcdWM1ZDAgXHVhZTMwXHVkNTU4XHVkNTU5XHViYjM4XHVjNTkxXHVjNzQ0IFx1Yzc5MFx1YjNkOVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM4ZmNcdWIyOTQgXHVjNWYwXHVhZDZjIFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1Yjk3YyBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1ZDY1OFx1Yzc3NFx1YWMwMCBcdWFkMDBcdWMyZWNcdWM3NDQgXHVhYzE2XHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjXHVjNjQwIFx1YzZkMFx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM3NzRcdWIyZTQuIG0gJnRpbWVzOyBuIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWIyOTQgXHVkNTVjIFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCZuYnNwO1x1YWMwMSBcdWQ1ODlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMThcdWIyOTQgblx1YWMxYywgXHVhYzAxIFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1YjI5NCBtXHVhYzFjXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzQwIHt2PHN1Yj5qPFwvc3ViPjxzdXA+aTxcL3N1cD4mbmJzcDs6IDAgJmxlOyBpICZsZTsgbS0xLCAwICZsZTsgaiAmbGU7IG4tMX0gXHVjNzNjXHViODVjLCBcdWFjMDRcdWMxMjBcdWM3NDAgeyh2PHN1Yj5qPFwvc3ViPjxzdXA+aTxcL3N1cD4sIHY8c3ViPnE8XC9zdWI+PHN1cD5wPFwvc3VwPikgOiB8aSAtIHB8ICsgfGogLSBxfCA9IDF9IFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gbSAmdGltZXM7IG4gXHVjNmQwXHVkNjE1IFx1YWRmOFx1YjlhY1x1YjRkY1x1YjI5NCBtICZ0aW1lczsgbiBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWNkOTRcdWFjMDBcdWQ1NzQgXHViM2Q5XHVhZGY4XHViNzk3XHVhYzhjIFx1YjljY1x1YjRlMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIDAgJmxlOyBpICZsZTsgbS0xXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgKHY8c3ViPm4tMTxcL3N1Yj48c3VwPmk8XC9zdXA+LCB2PHN1Yj4wPFwvc3ViPjxzdXA+aTxcL3N1cD4pXHViOTdjIFx1Y2Q5NFx1YWMwMFx1ZDU1YyBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWIyZTQuIDIgJnRpbWVzOyA2IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM2NDAgXHVjNmQwXHVkNjE1IFx1YWRmOFx1YjlhY1x1YjRkY1x1YjI5NCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIDFcdWFjZmMgMlx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljZVx1Yzc0MCBcdWFlMzBcdWQ1NThcdWQ1NTlcdWJiMzhcdWM1OTFcdWM3NDAgXHVhZGY4XHViOWFjXHViNGRjIFx1YzBjMVx1YzVkMFx1YzExYyBcdWMyYTRcdWQzMjhcdWIyZGQgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc3NFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWQyYjhcdWI5YWNcdWIyOTQgXHVjMGFjXHVjNzc0XHVkMDc0IFx1YzVjNlx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YmE3MCwgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWFjZmMgXHVjNzdjXHViZDgwIFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMyMThcdWQ2NThcdWM3NzRcdWIyOTQgMiAmdGltZXM7IG4gXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWMwMSBcdWM4MTVcdWM4MTBcdWM3NDAmbmJzcDtcdWIyZTRcdWI5NzggXHVjODE1XHVjODEwXHVhY2ZjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWJkODRcdWI0MWNcdWIyZTQuIFx1YWRmOFx1YjliYyAyXHVjNWQwIFx1YjA5OFx1YzY0MFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWIyZTRcdWI5NzggXHVhY2JkXHVjNmIwXHViODVjIFx1YzEzOFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgMiAmdGltZXM7IG4gXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzY0MCAyICZ0aW1lczsgbiBcdWM2ZDBcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9yc3AucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI2cHg7IHdpZHRoOjU1N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48c3Ryb25nPlx1YWRmOFx1YjliYyAxPFwvc3Ryb25nPi4gMiZuYnNwOyZ0aW1lczsgNiBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjXHVjNjQwIFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWQyYjhcdWI5YWMgXHVkNTVjIFx1YWMxYzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jc3AucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAwcHg7IHdpZHRoOjYxM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48c3Ryb25nPlx1YWRmOFx1YjliYyAyPFwvc3Ryb25nPi4gMiZuYnNwOyZ0aW1lczsgNiBcdWM2ZDBcdWQ2MTUgXHVhZGY4XHViOWFjXHViNGRjXHVjNjQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhYyBcdWI0NTAgXHVhYzFjPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgbiAmbGU7IDUwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBSPHN1Yj5uPFwvc3ViPlx1Yzc0NCAxMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1YzY0MCBDPHN1Yj5uPFwvc3ViPlx1Yzc0NCAxMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFI8c3ViPm48XC9zdWI+XHVjNzQwIDIgJnRpbWVzOyBuIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMTgsIEM8c3ViPm48XC9zdWI+XHVjNzQwIDIgJnRpbWVzOyBuIFx1YzZkMFx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTQ1NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikdlb21ldHJpYyBPcm5hbWVudHMiLCJkZXNjcmlwdGlvbiI6IjxwPk1hbmtpbmQgaGFzIGJlZW4gZGVjb3JhdGluZyBpdHMgb2JqZWN0cywgaXRzIGJ1aWxkaW5ncywgYW5kIGl0c2VsZiB0aHJvdWdob3V0IGFsbCBvZiBoaXN0b3J5IGFuZCBiYWNrIGludG8gcHJlaGlzdG9yeS4gR2VvbWV0cmljIG9ybmFtZW50cyBhcmUgdGhlIGVzc2VudGlhbCBlbGVtZW50cyBvZiBzdWNoIGRlY29yYXRpb24uIFdlIHNlZSB0aGVtIGV2ZXJ5IGRheSBhbmQgZXZlcnl3aGVyZSBhcm91bmQgdXMuIFNvb2h3YW4sIHdobyBpcyBhIGZhbW91cyBjb21wdXRhdGlvbmFsIGdlb21ldGVyLCBoYXMgcmVhbGl6ZWQgdGhhdCBnZW9tZXRyaWMgb3JuYW1lbnRzIGFyZSB2ZXJ5IHByZWNpc2UgZ2VvbWV0cmljIGNvbnN0cnVjdGlvbnMgYW5kIHRoZXkgYXJlIHVzdWFsbHkgYnVpbHQgb24gYSBiYXNlIG9mIGdyaWRzIGFuZCBtdWx0aXBsZSBzdWJncmlkcy4gUmVjZW50bHksIGhlIGluaXRpYXRlZCBhbiBhbWJpdGlvdXMgcmVzZWFyY2ggcHJvamVjdCBvbiB0aGUgYXV0b21hdGljIGdlbmVyYXRpb24gb2YgZ2VvbWV0cmljIG9ybmFtZW50cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW1vbmcgdmFyaW91cyBncmlkcywgdGhlIHJlY3Rhbmd1bGFyIGdyaWQgYW5kIHRoZSBjaXJjdWxhciBncmlkIGhhdmUgYXR0cmFjdGVkIGhpcyBhdHRlbnRpb24uIEFuIG0gJnRpbWVzOyBuIHJlY3Rhbmd1bGFyIGdyaWQgaXMgYSBncmFwaCB0aGF0IGNhbiBiZSBlbWJlZGRlZCBpbiB0aGUgcGxhbmUgc28gdGhhdCBpdHMgdmVydGljZXMgYW5kIGVkZ2VzIGZvcm0gYSByZWN0YW5ndWxhciBncmlkIHdpdGggbiB2ZXJ0aWNlcyBhcHBlYXJpbmcgaW4gZWFjaCBvZiBtIHJvd3MgYW5kIG0gdmVydGljZXMgYXBwZWFyaW5nIGluIGVhY2ggb2YgbiBjb2x1bW5zLiBNb3JlIHByZWNpc2VseSwgdGhlIG0gJnRpbWVzOyBuIHJlY3Rhbmd1bGFyIGdyaWQgaXMgdGhlIGdyYXBoIHdob3NlIHZlcnRleCBzZXQgaXMge3Y8c3ViPmo8XC9zdWI+PHN1cD5pPFwvc3VwPiZuYnNwOzogMCAmbGU7IGkgJmxlOyBtLTEsIDAgJmxlOyBqICZsZTsgbi0xfSZuYnNwO2FuZCB3aG9zZSBlZGdlIHNldCBpcyB7KHY8c3ViPmo8XC9zdWI+PHN1cD5pPFwvc3VwPiwgdjxzdWI+cTxcL3N1Yj48c3VwPnA8XC9zdXA+KSA6IHxpIC0gcHwgKyB8aiAtIHF8ID0gMX0uIFRoZSBtICZ0aW1lczsgbiBjaXJjdWxhciBncmlkIGlzIG9idGFpbmVkIGZyb20gdGhlIG0gJnRpbWVzOyBuIHJlY3Rhbmd1bGFyIGdyaWQgYnkgYWRkaW5nIHNvLWNhbGxlZCB3cmFwYXJvdW5kIGVkZ2VzICh2PHN1Yj5uLTE8XC9zdWI+PHN1cD5pPFwvc3VwPiwgdjxzdWI+MDxcL3N1Yj48c3VwPmk8XC9zdXA+KSBmb3IgZXZlcnkgMCAmbGU7IGkgJmxlOyBtLTEuIFRoZSAyICZ0aW1lczsgNiByZWN0YW5ndWxhciBncmlkIGFuZCB0aGUgMiAmdGltZXM7IDYgY2lyY3VsYXIgZ3JpZCBhcmUgc2hvd24gaW4gRmlndXJlcyAxIGFuZCAyLCByZXNwZWN0aXZlbHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvbWUgZ2VvbWV0cmljIG9ybmFtZW50cyBmb3JtIHNwYW5uaW5nIHRyZWVzIG9mIHRoZSB1bmRlcmx5aW5nIGdyaWQsIGFzIHNob3duIGluIEZpZ3VyZXMgMSBhbmQgMi4gSGVyZSwgYSBzcGFubmluZyB0cmVlIG9mIGEgZ3JpZCByZWZlcnMgdG8gYSB0cmVlLCBhIGNvbm5lY3RlZCBncmFwaCB3aXRob3V0IGN5Y2xlcywgY29tcG9zZWQgb2YgYWxsIHRoZSB2ZXJ0aWNlcyBhbmQgc29tZSBlZGdlcyBvZiB0aGUgZ3JpZC4gU29vaHdhbiB3YW50cyB0byBlbnVtZXJhdGUgYWxsIGRpZmZlcmVudCBsYWJlbGVkIHNwYW5uaW5nIHRyZWVzIG9mIHRoZSAyICZ0aW1lczsgbiBncmlkLCB3aGVyZSB0aGUgdmVydGljZXMgYXJlIGRpc3Rpbmd1aXNoZWQgZnJvbSBvbmUgYW5vdGhlciBieSBuYW1lcy4gKEVhY2ggdmVydGV4IGlzIGFzc2lnbmVkIGEgdW5pcXVlIG5hbWUgaW4gYSBsYWJlbGVkIGdyYXBoIHRvIGRpc3Rpbmd1aXNoIGl0IGZyb20gYWxsIG90aGVyIHZlcnRpY2VzLikgVGhlIHR3byBzcGFubmluZyB0cmVlcyBvZiB0aGUgMiAmdGltZXM7IDYgY2lyY3VsYXIgZ3JpZCBnaXZlbiBpbiBGaWd1cmUgMiBzaG91bGQgYmUgY291bnRlZCBzZXBhcmF0ZWx5LiBUbyBzdXBwb3J0IGhpcyBwcm9qZWN0LCB5b3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjb3VudCB0aGUgbnVtYmVycyBvZiBsYWJlbGVkIHNwYW5uaW5nIHRyZWVzIG9mIHRoZSAyICZ0aW1lczsgbiByZWN0YW5ndWxhciBncmlkIGFuZCBvZiB0aGUgMiAmdGltZXM7IG4gY2lyY3VsYXIgZ3JpZC4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9yc3AucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI2cHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDo1NTdweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48c3Ryb25nPkZpZ3VyZSAxPFwvc3Ryb25nPi4gQSAyICZ0aW1lczsgNiByZWN0YW5ndWxhciBncmlkIGFuZCBvbmUgb2YgaXRzIGxhYmVsZWQgc3Bhbm5pbmcgdHJlZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY3NwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwMHB4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6NjEzcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PHN0cm9uZz5GaWd1cmUgMjxcL3N0cm9uZz4uIEEgMiAmdGltZXM7IDYgY2lyY3VsYXIgZ3JpZCBhbmQgaXRzIHR3byBkaWZmZXJlbnQgbGFiZWxlZCBzcGFubmluZyB0cmVlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiwgaW5kaWNhdGluZyB0aGF0IHRoZSBkaW1lbnNpb24gb2YgdGhlIHVuZGVybHlpbmcgZ3JpZCBpcyAyICZ0aW1lczsgbiwgd2hlcmUgMyAmbGU7IG4gJmxlOyA1MCwwMDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0d28gaW50ZWdlcnMsIFI8c3ViPm48XC9zdWI+IG1vZHVsbyAxMCwwMDcgYW5kIEM8c3ViPm48XC9zdWI+IG1vZHVsbyAxMCwwMDcsIHdoZXJlIFI8c3ViPm48XC9zdWI+IGFuZCBDPHN1Yj5uPFwvc3ViPiBhcmUgcmVzcGVjdGl2ZWx5IHRoZSBudW1iZXJzIG9mIGxhYmVsZWQgc3Bhbm5pbmcgdHJlZXMgb2YgYSAyICZ0aW1lczsgbiByZWN0YW5ndWxhciBncmlkIGFuZCBvZiBhIDIgJnRpbWVzOyBuIGNpcmN1bGFyIGdyaWQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2013 C번