시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 115 34 27 31.765%

문제

상근이는 매우 큰 저택에 갇혔다. 이 저택은 정사각형 모양의 방이 격자 모양으로 배치되어 있고, N행 M열 형태이다. 왼쪽으로부터 x(1 ≤ x ≤ M)번째, 아래쪽으로부터 y(1 ≤ y ≤ N)번째 방을 (x,y)라고 한다.

모든 인접한 방의 사이에는 문이 있다. 문은 열려있을 수도 있고, 닫혀있을 수도 있다. 다른 방으로 이동하는데 걸리는 시간(문을 통과하는데 걸리는 시간)은 1분이다. 상근이는 항상 열려있는 문으로만 이동할 수 있고, 개폐 상태를 바꿀 수는 없다.

어떤 방의 중앙에는 스위치가 있다. 이 스위치를 1분동안 누르고 있으면, 집에 있는 모든 문의 개폐 상태가 바뀌게 된다. 즉, 열려있던 문은 닫히게 되고, 닫혀있던 문은 열리게 된다.

저택의 크기와 스위치가 있는 방의 정보가 주어진다. 상근이는 지금 (1,1)방의 중앙에 있고, (M,N)방의 중앙으로 이동하려고 한다. 이때, 이동할 수 있는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 

가장 처음에 위아래로 인접한 방의 문만 열려있고, 나머지 문은 모두 닫혀있다.

입력

첫째 줄에 집의 크기 M, N과 스위치가 있는 방의 수 K가 주어진다. 둘째 줄부터 K개 줄에는 스위치가 있는 방의 위치 (xi, yi)가 주어진다. (2 ≤ M,N ≤ 100,000, 1 ≤ K ≤ 200,000)

출력

첫째 줄에 가장 빠른 시간을 출력한다. 만약, (M,N)에 도착할 수 없는 경우에는 -1을 출력한다.

예제 입력 1

3 2 1
1 2

예제 출력 1

4

힌트

(1,1)번에서 (3,2)으로 4분만에 이동할 수 있다.

1. (1,2)로 이동

2. (1,2)에 있는 스위치를 누른다.

3. (2,2)로 이동

4. (3,2)로 이동

집의 모습은 아래 그림에 나타나 있다. ×는 상근이의 위치, ○는 스위치이다. 

또, 아래의 경우에 답은 25이다.

W3sicHJvYmxlbV9pZCI6IjU1MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDBcdWQwZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVkMDcwIFx1YzgwMFx1ZDBkZFx1YzVkMCBcdWFjMDdcdWQ2MTRcdWIyZTQuIFx1Yzc3NCBcdWM4MDBcdWQwZGRcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWJjMjlcdWM3NzQgXHVhY2E5XHVjNzkwIFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBOXHVkNTg5IE1cdWM1ZjQgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LiBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgeCgxICZsZTsgeCAmbGU7IE0pXHViYzg4XHVjOWY4LCBcdWM1NDRcdWI3OThcdWNhYmRcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgeSgxICZsZTsgeSAmbGU7IE4pXHViYzg4XHVjOWY4IFx1YmMyOVx1Yzc0NCAoeCx5KVx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViYzI5XHVjNzU4IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWJiMzhcdWM3NDAgXHVjNWY0XHViODI0XHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YjJlYlx1ZDYwMFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWIyZTRcdWI5NzggXHViYzI5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0KFx1YmIzOFx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNClcdWM3NDAgMVx1YmQ4NFx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMWNcdWQzZDAgXHVjMGMxXHVkMGRjXHViOTdjIFx1YmMxNFx1YWZjMCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1YjRcdWI1YTQgXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzVkMFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIDFcdWJkODRcdWIzZDlcdWM1NDggXHViMjA0XHViOTc0XHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3NCwgXHVjOWQxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViYjM4XHVjNzU4IFx1YWMxY1x1ZDNkMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHViYzE0XHViMDBjXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIzNTggXHViYjM4XHVjNzQwIFx1YjJlYlx1ZDc4OFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YjM1OCBcdWJiMzhcdWM3NDAgXHVjNWY0XHViOWFjXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODAwXHVkMGRkXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWMwXHVhZTA4ICgxLDEpXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzVkMCBcdWM3ODhcdWFjZTAsIChNLE4pXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzcwNFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViYzI5XHVjNzU4IFx1YmIzOFx1YjljYyBcdWM1ZjRcdWI4MjRcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWJiMzhcdWM3NDAgXHViYWE4XHViNDUwIFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWQxXHVjNzU4IFx1ZDA2Y1x1YWUzMCBNLCBOXHVhY2ZjIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzU4IFx1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM3MDRcdWNlNTggKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygyICZsZTsgTSxOICZsZTsgMTAwLDAwMCwgMSAmbGU7IEsgJmxlOyAyMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIChNLE4pXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdCgxLDEpXHViYzg4XHVjNWQwXHVjMTFjICgzLDIpXHVjNzNjXHViODVjIDRcdWJkODRcdWI5Y2NcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDEuICgxLDIpXHViODVjIFx1Yzc3NFx1YjNkOTxcL3A+XHJcbjxwPlxyXG5cdDIuICgxLDIpXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5N2MgXHViMjA0XHViOTc4XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdDMuICgyLDIpXHViODVjIFx1Yzc3NFx1YjNkOTxcL3A+XHJcbjxwPlxyXG5cdDQuICgzLDIpXHViODVjIFx1Yzc3NFx1YjNkOTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM5ZDFcdWM3NTggXHViYWE4XHVjMmI1XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC4gJnRpbWVzO1x1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNzA0XHVjZTU4LCBcdTI1Y2JcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N3LnBuZ1wiIHN0eWxlPVwid2lkdGg6IDY0N3B4OyBoZWlnaHQ6IDg3cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjYxMCwgXHVjNTQ0XHViNzk4XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWIyZjVcdWM3NDAgMjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3cyLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDMwNXB4OyBoZWlnaHQ6IDMzNXB4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTUyOSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1NzNmZVx1NGVlM1x1NzY4NFx1MzA2YVx1NWM0Ylx1NjU3NyAoTW9kZXJuIE1hbnNpb24pIiwiZGVzY3JpcHRpb24iOiI8cD5cdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdWZmMGNcdTMwNDJcdTMwOGJcdTU5MjdcdTMwNGRcdTMwNmFcdTVjNGJcdTY1NzdcdTMwNmJcdThmZjdcdTMwNDRcdThmYmNcdTMwOTNcdTMwNjdcdTMwNTdcdTMwN2VcdTMwNjNcdTMwNWZcdWZmMGVcdTMwNTNcdTMwNmVcdTVjNGJcdTY1NzdcdTMwNmZcdTZiNjNcdTY1YjlcdTVmNjJcdTMwNmVcdTkwZThcdTVjNGJcdTMwNGNcdTY3NzFcdTg5N2ZcdTUzNTdcdTUzMTdcdTMwNmJcdTY4M2NcdTViNTBcdTcyYjZcdTMwNmJcdWZmMGNcdTY3NzFcdTg5N2ZcdTY1YjlcdTU0MTFcdTMwNmIgTSBcdTUyMTdcdWZmMGNcdTUzNTdcdTUzMTdcdTY1YjlcdTU0MTFcdTMwNmIgTiBcdTg4NGNcdTMwNmVcdTU0MDhcdThhMDggTSBcdTAwMDIgTiBcdTUwMGJcdTRlMjZcdTMwOTNcdTMwNjBcdTY5Y2JcdTkwMjBcdTMwOTJcdTMwNTdcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTg5N2ZcdTMwNGJcdTMwODkgeCBcdTUyMTdcdTc2ZWUgKDEgJmxlOyB4ICZsZTsgTSlcdWZmMGNcdTUzNTdcdTMwNGJcdTMwODkgeSBcdTg4NGNcdTc2ZWUgKDEgJmxlOyB5ICZsZTsgTikgXHUzMDZiXHUzMDQyXHUzMDhiXHU5MGU4XHU1YzRiXHUzMDkyICh4LCB5KSBcdTMwNjdcdTg4NjhcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU2NzcxXHU4OTdmXHU1MzU3XHU1MzE3XHUzMDZiXHU5NmEzXHUzMDhhXHU1NDA4XHUzMDQ2IDIgXHU5MGU4XHU1YzRiXHUzMDZlXHU5NTkzXHUzMDZmXHVmZjBjXHU1OGMxXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDZiXHUzMDQyXHUzMDhiXHU2MjQ5XHUzMDZiXHUzMDg4XHUzMDhhXHU3ZDUwXHUzMDcwXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHUzMDZlXHU2MjQ5XHUzMDZmXHVmZjBjXHU5NTg5XHUzMDU4XHUzMDY2XHUzMDQ0XHUzMDY2XHU5MDFhXHU4ODRjXHU0ZTBkXHU1M2VmXHU4MGZkXHUzMDZhXHU3MmI2XHU2MTRiXHUzMDRiXHVmZjBjXHU5NThiXHUzMDQ0XHUzMDY2XHUzMDQ0XHUzMDY2XHU5MDFhXHU4ODRjXHU1M2VmXHU4MGZkXHUzMDZhXHU3MmI2XHU2MTRiXHUzMDZlXHUzMDQ0XHUzMDVhXHUzMDhjXHUzMDRiXHUzMDZiXHUzMDQyXHUzMDhiXHVmZjBlXHU2MjQ5XHUzMDRjXHU5NThiXHUzMDQ0XHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDY4XHUzMDRkXHVmZjBjXHUzMDVkXHUzMDhjXHUzMDg5XHUzMDZlXHU5MGU4XHU1YzRiXHUzMDZlXHU0ZTJkXHU1OTJlXHU5NTkzXHUzMDkyXHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHUzMDZlXHUzMDZiIDEgXHU1MjA2XHU5NTkzXHUzMDRiXHUzMDRiXHUzMDhiXHVmZjBlXHUzMDdlXHUzMDVmXHVmZjBjXHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU5MGU4XHU1YzRiXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDZiXHUzMDZmXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDRjXHUzMDQyXHUzMDhhXHVmZjBjXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDkyMSBcdTUyMDZcdTk1OTNcdTYyYmNcdTMwNTdcdTdkOWFcdTMwNTFcdTMwOGJcdTMwNjhcdWZmMGNcdTVjNGJcdTY1NzdcdTUxODVcdTMwNmVcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTYyNDlcdTMwNmVcdTk1OGJcdTk1ODlcdTMwNmVcdTcyYjZcdTYxNGJcdTMwNGNcdTUyMDdcdTMwOGFcdTY2ZmZcdTMwOGZcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU0ZWNhXHVmZjBjXHU2NzcxXHU4OTdmXHUzMDZiXHU5NmEzXHUzMDhhXHU1NDA4XHUzMDQ2IDIgXHU5MGU4XHU1YzRiXHUzMDkyXHU3ZDUwXHUzMDc2XHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHU2MjQ5XHUzMDZmXHU5NTg5XHUzMDU4XHUzMDY2XHUzMDQ0XHUzMDY2XHVmZjBjXHU1MzU3XHU1MzE3XHUzMDZiXHU5NmEzXHUzMDhhXHU1NDA4XHUzMDQ2IDIgXHU5MGU4XHU1YzRiXHUzMDkyXHU3ZDUwXHUzMDc2XHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHU2MjQ5XHUzMDZmXHU5NThiXHUzMDQ0XHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZmXHU0ZWNhXHU5MGU4XHU1YzRiICgxLCAxKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNmJcdTMwNDRcdTMwNjZcdWZmMGNcdTkwZThcdTVjNGIgKE0sIE4pIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA3ZVx1MzA2N1x1NjcwMFx1NzdlZFx1NjY0Mlx1OTU5M1x1MzA2N1x1NzlmYlx1NTJkNVx1MzA1N1x1MzA1Zlx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTVjNGJcdTY1NzdcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTUgTSwgTiBcdTMwNGFcdTMwODhcdTMwNzNcdWZmMGNcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGIgSyBcdTUwMGJcdTMwNmVcdTkwZThcdTVjNGJcdTMwNmVcdTRmNGRcdTdmNmUgKFg8c3ViPjE8XC9zdWI+LCBZPHN1Yj4xPFwvc3ViPiksKFg8c3ViPjI8XC9zdWI+LCBZPHN1Yj4yPFwvc3ViPiksIC4uLiAsIChYPHN1Yj5LPFwvc3ViPiwgWTxzdWI+SzxcL3N1Yj4pIFx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1ZmYwZVx1Njc3MVx1ODk3Zlx1MzA2Ylx1OTZhM1x1MzA4YVx1NTQwOFx1MzA0NiAyIFx1OTBlOFx1NWM0Ylx1MzA5Mlx1N2Q1MFx1MzA3Nlx1MzA1OVx1MzA3OVx1MzA2Nlx1MzA2ZVx1NjI0OVx1MzA2Zlx1OTU4OVx1MzA1OFx1MzA2Nlx1MzA0NFx1MzA2Nlx1ZmYwY1x1NTM1N1x1NTMxN1x1MzA2Ylx1OTZhM1x1MzA4YVx1NTQwOFx1MzA0NiAyIFx1OTBlOFx1NWM0Ylx1MzA5Mlx1N2Q1MFx1MzA3Nlx1MzA1OVx1MzA3OVx1MzA2Nlx1MzA2ZVx1NjI0OVx1MzA2Zlx1OTU4Ylx1MzA0NFx1MzA2Nlx1MzA0NFx1MzA4Ylx1NzJiNlx1NjE0Ylx1MzA0Ylx1MzA4OVx1NTljYlx1MzA4MVx1MzA2Nlx1ZmYwY1x1OTBlOFx1NWM0YiAoMSwgMSkgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDRiXHUzMDg5XHU5MGU4XHU1YzRiIChNLCBOKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwN2VcdTMwNjdcdTc5ZmJcdTUyZDVcdTMwNTlcdTMwOGJcdTMwNmVcdTMwNmJcdTY3MDBcdTc3ZWRcdTMwNjdcdTRmNTVcdTUyMDZcdTMwNGJcdTMwNGJcdTMwOGJcdTMwNGJcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTkwZThcdTVjNGIgKE0sIE4pIFx1MzA2Ylx1OGZiZlx1MzA4YVx1Nzc0MFx1MzA0Zlx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1MzA2OFx1MzA0ZFx1MzA2Zlx1MzA1ZFx1MzA4Y1x1MzA5Mlx1NjMwN1x1NjQ1OFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MTY1XHU1MjliXHUzMDRiXHUzMDg5XHU0ZWU1XHU0ZTBiXHUzMDZlXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDkyXHU4YWFkXHUzMDdmXHU4ZmJjXHUzMDgxXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGNcdTY1NzRcdTY1NzAgTSwgTiwgSyBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVNIFx1MzA2Zlx1NWM0Ylx1NjU3N1x1MzA2ZVx1Njc3MVx1ODk3Zlx1NjViOVx1NTQxMVx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NTAwYlx1NjU3MFx1ZmYwY04gXHUzMDZmXHU1YzRiXHU2NTc3XHUzMDZlXHU1MzU3XHU1MzE3XHU2NWI5XHU1NDExXHUzMDZlXHU5MGU4XHU1YzRiXHUzMDZlXHU1MDBiXHU2NTcwXHVmZjBjSyBcdTMwNmZcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU3ZDlhXHUzMDRmIEsgXHU4ODRjXHUzMDZlXHUzMDQ2XHUzMDYxXHUzMDZlIGkgXHU4ODRjXHU3NmVlICgxICZsZTsgaSAmbGU7IEspIFx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NjU3NFx1NjU3MCBYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj4gXHUzMDRjXHU3YTdhXHU3NjdkXHUzMDkyXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY4XHUzMDU3XHUzMDY2XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmXHVmZjBjXHU5MGU4XHU1YzRiIChYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj4pIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA2Ylx1MzBiOVx1MzBhNFx1MzBjM1x1MzBjMVx1MzA0Y1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZUsgXHU1MDBiXHUzMDZlXHU3ZDQ0IChYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pLCAoWDxzdWI+MjxcL3N1Yj4sIFk8c3ViPjI8XC9zdWI+KSwgLi4uICwgKFg8c3ViPks8XC9zdWI+LCBZPHN1Yj5LPFwvc3ViPikgXHUzMDZmXHU0ZTkyXHUzMDQ0XHUzMDZiXHU3NTcwXHUzMDZhXHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+MiAmbGU7IE0gJmxlOyAxMDAgMDAwIFx1NWM0Ylx1NjU3N1x1MzA2ZVx1Njc3MVx1ODk3Zlx1NjViOVx1NTQxMVx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NTAwYlx1NjU3MDxcL3A+XHJcblxyXG48cD4yICZsZTsgTiAmbGU7IDEwMCAwMDAgXHU1YzRiXHU2NTc3XHUzMDZlXHU1MzU3XHU1MzE3XHU2NWI5XHU1NDExXHUzMDZlXHU5MGU4XHU1YzRiXHUzMDZlXHU1MDBiXHU2NTcwPFwvcD5cclxuXHJcbjxwPjEgJmxlOyBLICZsZTsgMjAwIDAwMCBcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwNmVcdTUwMGJcdTY1NzA8XC9wPlxyXG5cclxuPHA+MSAmbGU7IFhpICZsZTsgTSBcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwNmVcdTY3NzFcdTg5N2ZcdTY1YjlcdTU0MTFcdTMwNmVcdTRmNGRcdTdmNmU8XC9wPlxyXG5cclxuPHA+MSAmbGU7IFlpICZsZTsgTiBcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwNmVcdTUzNTdcdTUzMTdcdTY1YjlcdTU0MTFcdTMwNmVcdTRmNGRcdTdmNmU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxZmFcdTUyOWJcdTMwNmJcdWZmMGNcdTc5ZmJcdTUyZDVcdTMwNmJcdTY3MDBcdTc3ZWRcdTMwNjdcdTRmNTVcdTUyMDZcdTMwNGJcdTMwNGJcdTMwOGJcdTMwNGJcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTkwZThcdTVjNGIgKE0sIE4pIFx1MzA2Ylx1OGZiZlx1MzA4YVx1Nzc0MFx1MzA0Zlx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1MzA2OFx1MzA0ZFx1MzA2Zlx1NGVlM1x1MzA4Zlx1MzA4YVx1MzA2Ylx1NjU3NFx1NjU3MCAxIFx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdTMwNTNcdTMwNmVcdTRmOGJcdTMwNjdcdTMwNmZcdWZmMGNcdTRlZTVcdTRlMGJcdTMwNmVcdTg4NGNcdTUyZDVcdTMwNmJcdTMwODhcdTMwNjNcdTMwNjYgNCBcdTUyMDZcdTk1OTNcdTMwNjdcdTkwZThcdTVjNGIgKDEsIDEpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA0Ylx1MzA4OVx1OTBlOFx1NWM0YiAoMywgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHVmZjBjXHUzMDUzXHUzMDhjXHUzMDRjXHU2NzAwXHU3N2VkXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1OTBlOFx1NWM0YiAoMSwgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHVmZjBlPGJyIFwvPlxyXG5cdTkwZThcdTVjNGIgKDEsIDIpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA2ZVx1MzBiOVx1MzBhNFx1MzBjM1x1MzBjMVx1MzA5Mlx1NjJiY1x1MzA1OVx1ZmYwZTxiciBcLz5cclxuXHU5MGU4XHU1YzRiICgyLCAyKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNzhcdTc5ZmJcdTUyZDVcdTMwNTlcdTMwOGJcdWZmMGU8YnIgXC8+XHJcblx1OTBlOFx1NWM0YiAoMywgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzA1M1x1MzA2ZVx1MzA2OFx1MzA0ZFx1MzA2ZVx1NWM0Ylx1NjU3N1x1MzA2ZVx1NjlkOFx1NWI1MFx1MzA0Y1x1NGVlNVx1NGUwYlx1MzA2ZVx1NTZmM1x1MzA2Ylx1ODg2OFx1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1NTZmM1x1MzA2N1x1MzA2Zlx1NTNmM1x1NjViOVx1NTQxMVx1MzA0Y1x1Njc3MVx1ZmYwY1x1NGUwYVx1NjViOVx1NTQxMVx1MzA0Y1x1NTMxN1x1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwYyZ0aW1lcztcdTUzNzBcdTMwNmZcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmVcdTRmNGRcdTdmNmVcdWZmMGNcdTI1Y2JcdTUzNzBcdTMwNmZcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdy5wbmdcIiBzdHlsZT1cImhlaWdodDo4N3B4OyB3aWR0aDo2NDdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 > JOI 2013 3번