시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB103816912718.759%

문제

상근이는 매우 큰 저택에 갇혔다. 이 저택은 정사각형 모양의 방이 격자 모양으로 배치되어 있고, 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)로 이동

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

예제 입력 2

3 2 1
2 1

예제 출력 2

-1

예제 입력 3

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

예제 출력 3

25

W3sicHJvYmxlbV9pZCI6IjU1MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDBcdWQwZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVkMDcwIFx1YzgwMFx1ZDBkZFx1YzVkMCBcdWFjMDdcdWQ2MTRcdWIyZTQuIFx1Yzc3NCBcdWM4MDBcdWQwZGRcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWJjMjlcdWM3NzQgXHVhY2E5XHVjNzkwIFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBOXHVkNTg5IE1cdWM1ZjQgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LiBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgeCgxICZsZTsgeCAmbGU7IE0pXHViYzg4XHVjOWY4LCBcdWM1NDRcdWI3OThcdWNhYmRcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgeSgxICZsZTsgeSAmbGU7IE4pXHViYzg4XHVjOWY4IFx1YmMyOVx1Yzc0NCAoeCx5KVx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViYzI5XHVjNzU4IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWJiMzhcdWM3NDAgXHVjNWY0XHViODI0XHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YjJlYlx1ZDYwMFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWIyZTRcdWI5NzggXHViYzI5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0KFx1YmIzOFx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNClcdWM3NDAgMVx1YmQ4NFx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMWNcdWQzZDAgXHVjMGMxXHVkMGRjXHViOTdjIFx1YmMxNFx1YWZjMCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzVkMFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIDFcdWJkODRcdWIzZDlcdWM1NDggXHViMjA0XHViOTc0XHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3NCwgXHVjOWQxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViYjM4XHVjNzU4IFx1YWMxY1x1ZDNkMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHViYzE0XHViMDBjXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIzNTggXHViYjM4XHVjNzQwIFx1YjJlYlx1ZDc4OFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YjM1OCBcdWJiMzhcdWM3NDAgXHVjNWY0XHViOWFjXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODAwXHVkMGRkXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWMwXHVhZTA4ICgxLDEpXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzVkMCBcdWM3ODhcdWFjZTAsIChNLE4pXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzcwNFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViYzI5XHVjNzU4IFx1YmIzOFx1YjljYyBcdWM1ZjRcdWI4MjRcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWJiMzhcdWM3NDAgXHViYWE4XHViNDUwIFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWQxXHVjNzU4IFx1ZDA2Y1x1YWUzMCBNLCBOXHVhY2ZjIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzU4IFx1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM3MDRcdWNlNTggKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygyICZsZTsgTSxOICZsZTsgMTAwLDAwMCwgMSAmbGU7IEsgJmxlOyAyMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIChNLE4pXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPigxLDEpXHViYzg4XHVjNWQwXHVjMTFjICgzLDIpXHVjNzNjXHViODVjIDRcdWJkODRcdWI5Y2NcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+KDEsMilcdWI4NWMgXHVjNzc0XHViM2Q5PFwvbGk+XHJcblx0PGxpPigxLDIpXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5N2MgXHViMjA0XHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4oMiwyKVx1Yjg1YyBcdWM3NzRcdWIzZDk8XC9saT5cclxuXHQ8bGk+KDMsMilcdWI4NWMgXHVjNzc0XHViM2Q5PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjOWQxXHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc0MCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjA5OCBcdWM3ODhcdWIyZTQuICZ0aW1lcztcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzcwNFx1Y2U1OCwgXHUyNWNiXHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84MDRmYTY3Ny1mZTY1LTQzNmYtYjEyZC1lYmNlNTQxNGYwMTVcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDYzNnB4OyBoZWlnaHQ6IDgwcHg7XCIgXC8+PFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZTA0YTYzMTYtYzU2Yi00NjNiLWFlNzMtOTI1M2RkZDIxMmM4XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNzlweDsgaGVpZ2h0OiAzMTRweDtcIiBcLz48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiI1NTI5IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHU3M2ZlXHU0ZWUzXHU3Njg0XHUzMDZhXHU1YzRiXHU2NTc3IChNb2Rlcm4gTWFuc2lvbikiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Zlx1ZmYwY1x1MzA0Mlx1MzA4Ylx1NTkyN1x1MzA0ZFx1MzA2YVx1NWM0Ylx1NjU3N1x1MzA2Ylx1OGZmN1x1MzA0NFx1OGZiY1x1MzA5M1x1MzA2N1x1MzA1N1x1MzA3ZVx1MzA2M1x1MzA1Zlx1ZmYwZVx1MzA1M1x1MzA2ZVx1NWM0Ylx1NjU3N1x1MzA2Zlx1NmI2M1x1NjViOVx1NWY2Mlx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA0Y1x1Njc3MVx1ODk3Zlx1NTM1N1x1NTMxN1x1MzA2Ylx1NjgzY1x1NWI1MFx1NzJiNlx1MzA2Ylx1ZmYwY1x1Njc3MVx1ODk3Zlx1NjViOVx1NTQxMVx1MzA2YiBNIFx1NTIxN1x1ZmYwY1x1NTM1N1x1NTMxN1x1NjViOVx1NTQxMVx1MzA2YiBOIFx1ODg0Y1x1MzA2ZVx1NTQwOFx1OGEwOCBNIFx1MDAwMiBOIFx1NTAwYlx1NGUyNlx1MzA5M1x1MzA2MFx1NjljYlx1OTAyMFx1MzA5Mlx1MzA1N1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1ODk3Zlx1MzA0Ylx1MzA4OSB4IFx1NTIxN1x1NzZlZSAoMSAmbGU7IHggJmxlOyBNKVx1ZmYwY1x1NTM1N1x1MzA0Ylx1MzA4OSB5IFx1ODg0Y1x1NzZlZSAoMSAmbGU7IHkgJmxlOyBOKSBcdTMwNmJcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwOTIgKHgsIHkpIFx1MzA2N1x1ODg2OFx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTY3NzFcdTg5N2ZcdTUzNTdcdTUzMTdcdTMwNmJcdTk2YTNcdTMwOGFcdTU0MDhcdTMwNDYgMiBcdTkwZThcdTVjNGJcdTMwNmVcdTk1OTNcdTMwNmZcdWZmMGNcdTU4YzFcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNmJcdTMwNDJcdTMwOGJcdTYyNDlcdTMwNmJcdTMwODhcdTMwOGFcdTdkNTBcdTMwNzBcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdTYyNDlcdTMwNmZcdWZmMGNcdTk1ODlcdTMwNThcdTMwNjZcdTMwNDRcdTMwNjZcdTkwMWFcdTg4NGNcdTRlMGRcdTUzZWZcdTgwZmRcdTMwNmFcdTcyYjZcdTYxNGJcdTMwNGJcdWZmMGNcdTk1OGJcdTMwNDRcdTMwNjZcdTMwNDRcdTMwNjZcdTkwMWFcdTg4NGNcdTUzZWZcdTgwZmRcdTMwNmFcdTcyYjZcdTYxNGJcdTMwNmVcdTMwNDRcdTMwNWFcdTMwOGNcdTMwNGJcdTMwNmJcdTMwNDJcdTMwOGJcdWZmMGVcdTYyNDlcdTMwNGNcdTk1OGJcdTMwNDRcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNjhcdTMwNGRcdWZmMGNcdTMwNWRcdTMwOGNcdTMwODlcdTMwNmVcdTkwZThcdTVjNGJcdTMwNmVcdTRlMmRcdTU5MmVcdTk1OTNcdTMwOTJcdTc5ZmJcdTUyZDVcdTMwNTlcdTMwOGJcdTMwNmVcdTMwNmIgMSBcdTUyMDZcdTk1OTNcdTMwNGJcdTMwNGJcdTMwOGJcdWZmMGVcdTMwN2VcdTMwNWZcdWZmMGNcdTMwNDRcdTMwNGZcdTMwNjRcdTMwNGJcdTMwNmVcdTkwZThcdTVjNGJcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNmJcdTMwNmZcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNGNcdTMwNDJcdTMwOGFcdWZmMGNcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwOTIxIFx1NTIwNlx1OTU5M1x1NjJiY1x1MzA1N1x1N2Q5YVx1MzA1MVx1MzA4Ylx1MzA2OFx1ZmYwY1x1NWM0Ylx1NjU3N1x1NTE4NVx1MzA2ZVx1MzA1OVx1MzA3OVx1MzA2Nlx1MzA2ZVx1NjI0OVx1MzA2ZVx1OTU4Ylx1OTU4OVx1MzA2ZVx1NzJiNlx1NjE0Ylx1MzA0Y1x1NTIwN1x1MzA4YVx1NjZmZlx1MzA4Zlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTRlY2FcdWZmMGNcdTY3NzFcdTg5N2ZcdTMwNmJcdTk2YTNcdTMwOGFcdTU0MDhcdTMwNDYgMiBcdTkwZThcdTVjNGJcdTMwOTJcdTdkNTBcdTMwNzZcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTYyNDlcdTMwNmZcdTk1ODlcdTMwNThcdTMwNjZcdTMwNDRcdTMwNjZcdWZmMGNcdTUzNTdcdTUzMTdcdTMwNmJcdTk2YTNcdTMwOGFcdTU0MDhcdTMwNDYgMiBcdTkwZThcdTVjNGJcdTMwOTJcdTdkNTBcdTMwNzZcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTYyNDlcdTMwNmZcdTk1OGJcdTMwNDRcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTRlY2FcdTkwZThcdTVjNGIgKDEsIDEpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA2Ylx1MzA0NFx1MzA2Nlx1ZmYwY1x1OTBlOFx1NWM0YiAoTSwgTikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDdlXHUzMDY3XHU2NzAwXHU3N2VkXHU2NjQyXHU5NTkzXHUzMDY3XHU3OWZiXHU1MmQ1XHUzMDU3XHUzMDVmXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NWM0Ylx1NjU3N1x1MzA2ZVx1NTkyN1x1MzA0ZFx1MzA1NSBNLCBOIFx1MzA0YVx1MzA4OFx1MzA3M1x1ZmYwY1x1MzBiOVx1MzBhNFx1MzBjM1x1MzBjMVx1MzA2ZVx1MzA0Mlx1MzA4YiBLIFx1NTAwYlx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NGY0ZFx1N2Y2ZSAoWDxzdWI+MTxcL3N1Yj4sIFk8c3ViPjE8XC9zdWI+KSwoWDxzdWI+MjxcL3N1Yj4sIFk8c3ViPjI8XC9zdWI+KSwgLi4uICwgKFg8c3ViPks8XC9zdWI+LCBZPHN1Yj5LPFwvc3ViPikgXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHVmZjBlXHU2NzcxXHU4OTdmXHUzMDZiXHU5NmEzXHUzMDhhXHU1NDA4XHUzMDQ2IDIgXHU5MGU4XHU1YzRiXHUzMDkyXHU3ZDUwXHUzMDc2XHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHU2MjQ5XHUzMDZmXHU5NTg5XHUzMDU4XHUzMDY2XHUzMDQ0XHUzMDY2XHVmZjBjXHU1MzU3XHU1MzE3XHUzMDZiXHU5NmEzXHUzMDhhXHU1NDA4XHUzMDQ2IDIgXHU5MGU4XHU1YzRiXHUzMDkyXHU3ZDUwXHUzMDc2XHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHU2MjQ5XHUzMDZmXHU5NThiXHUzMDQ0XHUzMDY2XHUzMDQ0XHUzMDhiXHU3MmI2XHU2MTRiXHUzMDRiXHUzMDg5XHU1OWNiXHUzMDgxXHUzMDY2XHVmZjBjXHU5MGU4XHU1YzRiICgxLCAxKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNGJcdTMwODlcdTkwZThcdTVjNGIgKE0sIE4pIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA3ZVx1MzA2N1x1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1MzA2ZVx1MzA2Ylx1NjcwMFx1NzdlZFx1MzA2N1x1NGY1NVx1NTIwNlx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzA0Ylx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZVx1MzA1Zlx1MzA2MFx1MzA1N1x1ZmYwY1x1OTBlOFx1NWM0YiAoTSwgTikgXHUzMDZiXHU4ZmJmXHUzMDhhXHU3NzQwXHUzMDRmXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHUzMDY4XHUzMDRkXHUzMDZmXHUzMDVkXHUzMDhjXHUzMDkyXHU2MzA3XHU2NDU4XHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NjU3NFx1NjU3MCBNLCBOLCBLIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZU0gXHUzMDZmXHU1YzRiXHU2NTc3XHUzMDZlXHU2NzcxXHU4OTdmXHU2NWI5XHU1NDExXHUzMDZlXHU5MGU4XHU1YzRiXHUzMDZlXHU1MDBiXHU2NTcwXHVmZjBjTiBcdTMwNmZcdTVjNGJcdTY1NzdcdTMwNmVcdTUzNTdcdTUzMTdcdTY1YjlcdTU0MTFcdTMwNmVcdTkwZThcdTVjNGJcdTMwNmVcdTUwMGJcdTY1NzBcdWZmMGNLIFx1MzA2Zlx1MzBiOVx1MzBhNFx1MzBjM1x1MzBjMVx1MzA2ZVx1MzA0Mlx1MzA4Ylx1OTBlOFx1NWM0Ylx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgSyBcdTg4NGNcdTMwNmVcdTMwNDZcdTMwNjFcdTMwNmUgaSBcdTg4NGNcdTc2ZWUgKDEgJmxlOyBpICZsZTsgSykgXHUzMDZiXHUzMDZmXHVmZjBjXHU2NTc0XHU2NTcwIFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdWZmMGNcdTkwZThcdTVjNGIgKFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDZiXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDRjXHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlSyBcdTUwMGJcdTMwNmVcdTdkNDQgKFg8c3ViPjE8XC9zdWI+LCBZPHN1Yj4xPFwvc3ViPiksIChYPHN1Yj4yPFwvc3ViPiwgWTxzdWI+MjxcL3N1Yj4pLCAuLi4gLCAoWDxzdWI+SzxcL3N1Yj4sIFk8c3ViPks8XC9zdWI+KSBcdTMwNmZcdTRlOTJcdTMwNDRcdTMwNmJcdTc1NzBcdTMwNmFcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY1x1NzlmYlx1NTJkNVx1MzA2Ylx1NjcwMFx1NzdlZFx1MzA2N1x1NGY1NVx1NTIwNlx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzA0Ylx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MFx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZVx1MzA1Zlx1MzA2MFx1MzA1N1x1ZmYwY1x1OTBlOFx1NWM0YiAoTSwgTikgXHUzMDZiXHU4ZmJmXHUzMDhhXHU3NzQwXHUzMDRmXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHUzMDY4XHUzMDRkXHUzMDZmXHU0ZWUzXHUzMDhmXHUzMDhhXHUzMDZiXHU2NTc0XHU2NTcwIDEgXHUzMDkyXHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiSmFwYW5lc2UiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MiAmbGU7IE0gJmxlOyAxMDAgMDAwIFx1NWM0Ylx1NjU3N1x1MzA2ZVx1Njc3MVx1ODk3Zlx1NjViOVx1NTQxMVx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NTAwYlx1NjU3MDxcL2xpPlxyXG5cdDxsaT4yICZsZTsgTiAmbGU7IDEwMCAwMDAgXHU1YzRiXHU2NTc3XHUzMDZlXHU1MzU3XHU1MzE3XHU2NWI5XHU1NDExXHUzMDZlXHU5MGU4XHU1YzRiXHUzMDZlXHU1MDBiXHU2NTcwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBLICZsZTsgMjAwIDAwMCBcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwNmVcdTUwMGJcdTY1NzA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFg8c3ViPmk8XC9zdWI+ICZsZTsgTSBcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwNmVcdTY3NzFcdTg5N2ZcdTY1YjlcdTU0MTFcdTMwNmVcdTRmNGRcdTdmNmU8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFk8c3ViPmk8XC9zdWI+ICZsZTsgTiBcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNmVcdTMwNDJcdTMwOGJcdTkwZThcdTVjNGJcdTMwNmVcdTUzNTdcdTUzMTdcdTY1YjlcdTU0MTFcdTMwNmVcdTRmNGRcdTdmNmU8XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdTMwNTNcdTMwNmVcdTRmOGJcdTMwNjdcdTMwNmZcdWZmMGNcdTRlZTVcdTRlMGJcdTMwNmVcdTg4NGNcdTUyZDVcdTMwNmJcdTMwODhcdTMwNjNcdTMwNjYgNCBcdTUyMDZcdTk1OTNcdTMwNjdcdTkwZThcdTVjNGIgKDEsIDEpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA0Ylx1MzA4OVx1OTBlOFx1NWM0YiAoMywgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHVmZjBjIFx1MzA1M1x1MzA4Y1x1MzA0Y1x1NjcwMFx1NzdlZFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1OTBlOFx1NWM0YiAoMSwgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPlx1OTBlOFx1NWM0YiAoMSwgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDZlXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDkyXHU2MmJjXHUzMDU5XHVmZjBlPFwvbGk+XHJcblx0PGxpPlx1OTBlOFx1NWM0YiAoMiwgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPlx1OTBlOFx1NWM0YiAoMywgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHUzMDUzXHUzMDZlXHUzMDY4XHUzMDRkXHUzMDZlXHU1YzRiXHU2NTc3XHUzMDZlXHU2OWQ4XHU1YjUwXHUzMDRjXHU0ZWU1XHU0ZTBiXHUzMDZlXHU1NmYzXHUzMDZiXHU4ODY4XHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU1NmYzXHUzMDY3XHUzMDZmXHU1M2YzXHU2NWI5XHU1NDExXHUzMDRjXHU2NzcxXHVmZjBjXHU0ZTBhXHU2NWI5XHU1NDExXHUzMDRjXHU1MzE3XHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjJnRpbWVzO1x1NTM3MFx1MzA2Zlx1MzA0Mlx1MzA2YSBcdTMwNWZcdTMwNmVcdTRmNGRcdTdmNmVcdWZmMGNcdTI1Y2JcdTUzNzBcdTMwNmZcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84MDRmYTY3Ny1mZTY1LTQzNmYtYjEyZC1lYmNlNTQxNGYwMTVcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDYzNnB4OyBoZWlnaHQ6IDgwcHg7XCIgXC8+PFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlx1MzA1M1x1MzA2ZVx1NGY4Ylx1MzA2N1x1MzA2Zlx1ZmYwY1x1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Zlx1OTBlOFx1NWM0YiAoMywgMikgXHUzMDZiXHU4ZmJmXHUzMDhhXHU3NzQwXHUzMDRmXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPlx1MzA1M1x1MzA2ZVx1NGY4Ylx1MzA2N1x1MzA2Zlx1ZmYwY1x1NjcwMFx1NTIxZFx1MzA2ZVx1NWM0Ylx1NjU3N1x1MzA2ZVx1NjlkOFx1NWI1MFx1MzA2Zlx1NGVlNVx1NGUwYlx1MzA2ZVx1NTZmM1x1MzA2ZVx1MzA4OFx1MzA0Nlx1MzA2Ylx1MzA2YVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1OTBlOFx1NWM0YiAoMSwgMSkgXHUzMDg0XHU5MGU4XHU1YzRiIChNLCBOKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNmJcdTMwYjlcdTMwYTRcdTMwYzMgXHUzMGMxXHUzMDRjXHUzMDQyXHUzMDhiXHU1M2VmXHU4MGZkXHU2MDI3XHUzMDgyXHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHU2Y2U4XHU2MTBmXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZTA0YTYzMTYtYzU2Yi00NjNiLWFlNzMtOTI1M2RkZDIxMmM4XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNzlweDsgaGVpZ2h0OiAzMTRweDtcIiBcLz48XC9wPlxyXG4ifV0=

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2012/2013 3번