시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 113 32 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+XHJcblx0XHVjODAwXHVkMGRkXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWMwXHVhZTA4ICgxLDEpXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzVkMCBcdWM3ODhcdWFjZTAsIChNLE4pXHViYzI5XHVjNzU4IFx1YzkxMVx1YzU1OVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWM3MDRcdWM1NDRcdWI3OThcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YmMyOVx1Yzc1OCBcdWJiMzhcdWI5Y2MgXHVjNWY0XHViODI0XHVjNzg4XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHViYjM4XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZWJcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzlkMVx1Yzc1OCBcdWQwNmNcdWFlMzAgTSwgTlx1YWNmYyBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgS1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM3NTggXHVjNzA0XHVjZTU4ICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMiAmbGU7IE0sTiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBLICZsZTsgMjAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCAoTSxOKVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHQoMSwxKVx1YmM4OFx1YzVkMFx1YzExYyAoMywyKVx1YzczY1x1Yjg1YyA0XHViZDg0XHViOWNjXHVjNWQwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxLiAoMSwyKVx1Yjg1YyBcdWM3NzRcdWIzZDk8XC9wPlxyXG48cD5cclxuXHQyLiAoMSwyKVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1YjIwNFx1Yjk3OFx1YjJlNC48XC9wPlxyXG48cD5cclxuXHQzLiAoMiwyKVx1Yjg1YyBcdWM3NzRcdWIzZDk8XC9wPlxyXG48cD5cclxuXHQ0LiAoMywyKVx1Yjg1YyBcdWM3NzRcdWIzZDk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjOWQxXHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc0MCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjA5OCBcdWM3ODhcdWIyZTQuICZ0aW1lcztcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzcwNFx1Y2U1OCwgXHUyNWNiXHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdy5wbmdcIiBzdHlsZT1cIndpZHRoOiA2NDdweDsgaGVpZ2h0OiA4N3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI2MTAsIFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViMmY1XHVjNzQwIDI1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N3Mi5wbmdcIiBzdHlsZT1cIndpZHRoOiAzMDVweDsgaGVpZ2h0OiAzMzVweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1MjkiLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJcdTczZmVcdTRlZTNcdTc2ODRcdTMwNmFcdTVjNGJcdTY1NzcgKE1vZGVybiBNYW5zaW9uKSIsImRlc2NyaXB0aW9uIjoiPHA+XHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZmXHVmZjBjXHUzMDQyXHUzMDhiXHU1OTI3XHUzMDRkXHUzMDZhXHU1YzRiXHU2NTc3XHUzMDZiXHU4ZmY3XHUzMDQ0XHU4ZmJjXHUzMDkzXHUzMDY3XHUzMDU3XHUzMDdlXHUzMDYzXHUzMDVmXHVmZjBlXHUzMDUzXHUzMDZlXHU1YzRiXHU2NTc3XHUzMDZmXHU2YjYzXHU2NWI5XHU1ZjYyXHUzMDZlXHU5MGU4XHU1YzRiXHUzMDRjXHU2NzcxXHU4OTdmXHU1MzU3XHU1MzE3XHUzMDZiXHU2ODNjXHU1YjUwXHU3MmI2XHUzMDZiXHVmZjBjXHU2NzcxXHU4OTdmXHU2NWI5XHU1NDExXHUzMDZiIE0gXHU1MjE3XHVmZjBjXHU1MzU3XHU1MzE3XHU2NWI5XHU1NDExXHUzMDZiIE4gXHU4ODRjXHUzMDZlXHU1NDA4XHU4YTA4IE0gXHUwMDAyIE4gXHU1MDBiXHU0ZTI2XHUzMDkzXHUzMDYwXHU2OWNiXHU5MDIwXHUzMDkyXHUzMDU3XHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU4OTdmXHUzMDRiXHUzMDg5IHggXHU1MjE3XHU3NmVlICgxICZsZTsgeCAmbGU7IE0pXHVmZjBjXHU1MzU3XHUzMDRiXHUzMDg5IHkgXHU4ODRjXHU3NmVlICgxICZsZTsgeSAmbGU7IE4pIFx1MzA2Ylx1MzA0Mlx1MzA4Ylx1OTBlOFx1NWM0Ylx1MzA5MiAoeCwgeSkgXHUzMDY3XHU4ODY4XHUzMDU5XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1Njc3MVx1ODk3Zlx1NTM1N1x1NTMxN1x1MzA2Ylx1OTZhM1x1MzA4YVx1NTQwOFx1MzA0NiAyIFx1OTBlOFx1NWM0Ylx1MzA2ZVx1OTU5M1x1MzA2Zlx1ZmYwY1x1NThjMVx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA2Ylx1MzA0Mlx1MzA4Ylx1NjI0OVx1MzA2Ylx1MzA4OFx1MzA4YVx1N2Q1MFx1MzA3MFx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1MzA2ZVx1NjI0OVx1MzA2Zlx1ZmYwY1x1OTU4OVx1MzA1OFx1MzA2Nlx1MzA0NFx1MzA2Nlx1OTAxYVx1ODg0Y1x1NGUwZFx1NTNlZlx1ODBmZFx1MzA2YVx1NzJiNlx1NjE0Ylx1MzA0Ylx1ZmYwY1x1OTU4Ylx1MzA0NFx1MzA2Nlx1MzA0NFx1MzA2Nlx1OTAxYVx1ODg0Y1x1NTNlZlx1ODBmZFx1MzA2YVx1NzJiNlx1NjE0Ylx1MzA2ZVx1MzA0NFx1MzA1YVx1MzA4Y1x1MzA0Ylx1MzA2Ylx1MzA0Mlx1MzA4Ylx1ZmYwZVx1NjI0OVx1MzA0Y1x1OTU4Ylx1MzA0NFx1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA2OFx1MzA0ZFx1ZmYwY1x1MzA1ZFx1MzA4Y1x1MzA4OVx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NGUyZFx1NTkyZVx1OTU5M1x1MzA5Mlx1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1MzA2ZVx1MzA2YiAxIFx1NTIwNlx1OTU5M1x1MzA0Ylx1MzA0Ylx1MzA4Ylx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY1x1MzA0NFx1MzA0Zlx1MzA2NFx1MzA0Ylx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA2Ylx1MzA2Zlx1MzBiOVx1MzBhNFx1MzBjM1x1MzBjMVx1MzA0Y1x1MzA0Mlx1MzA4YVx1ZmYwY1x1MzBiOVx1MzBhNFx1MzBjM1x1MzBjMVx1MzA5MjEgXHU1MjA2XHU5NTkzXHU2MmJjXHUzMDU3XHU3ZDlhXHUzMDUxXHUzMDhiXHUzMDY4XHVmZjBjXHU1YzRiXHU2NTc3XHU1MTg1XHUzMDZlXHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHU2MjQ5XHUzMDZlXHU5NThiXHU5NTg5XHUzMDZlXHU3MmI2XHU2MTRiXHUzMDRjXHU1MjA3XHUzMDhhXHU2NmZmXHUzMDhmXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NGVjYVx1ZmYwY1x1Njc3MVx1ODk3Zlx1MzA2Ylx1OTZhM1x1MzA4YVx1NTQwOFx1MzA0NiAyIFx1OTBlOFx1NWM0Ylx1MzA5Mlx1N2Q1MFx1MzA3Nlx1MzA1OVx1MzA3OVx1MzA2Nlx1MzA2ZVx1NjI0OVx1MzA2Zlx1OTU4OVx1MzA1OFx1MzA2Nlx1MzA0NFx1MzA2Nlx1ZmYwY1x1NTM1N1x1NTMxN1x1MzA2Ylx1OTZhM1x1MzA4YVx1NTQwOFx1MzA0NiAyIFx1OTBlOFx1NWM0Ylx1MzA5Mlx1N2Q1MFx1MzA3Nlx1MzA1OVx1MzA3OVx1MzA2Nlx1MzA2ZVx1NjI0OVx1MzA2Zlx1OTU4Ylx1MzA0NFx1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Zlx1NGVjYVx1OTBlOFx1NWM0YiAoMSwgMSkgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDZiXHUzMDQ0XHUzMDY2XHVmZjBjXHU5MGU4XHU1YzRiIChNLCBOKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwN2VcdTMwNjdcdTY3MDBcdTc3ZWRcdTY2NDJcdTk1OTNcdTMwNjdcdTc5ZmJcdTUyZDVcdTMwNTdcdTMwNWZcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1YzRiXHU2NTc3XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDU1IE0sIE4gXHUzMDRhXHUzMDg4XHUzMDczXHVmZjBjXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDZlXHUzMDQyXHUzMDhiIEsgXHU1MDBiXHUzMDZlXHU5MGU4XHU1YzRiXHUzMDZlXHU0ZjRkXHU3ZjZlIChYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pLChYPHN1Yj4yPFwvc3ViPiwgWTxzdWI+MjxcL3N1Yj4pLCAuLi4gLCAoWDxzdWI+SzxcL3N1Yj4sIFk8c3ViPks8XC9zdWI+KSBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdWZmMGVcdTY3NzFcdTg5N2ZcdTMwNmJcdTk2YTNcdTMwOGFcdTU0MDhcdTMwNDYgMiBcdTkwZThcdTVjNGJcdTMwOTJcdTdkNTBcdTMwNzZcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTYyNDlcdTMwNmZcdTk1ODlcdTMwNThcdTMwNjZcdTMwNDRcdTMwNjZcdWZmMGNcdTUzNTdcdTUzMTdcdTMwNmJcdTk2YTNcdTMwOGFcdTU0MDhcdTMwNDYgMiBcdTkwZThcdTVjNGJcdTMwOTJcdTdkNTBcdTMwNzZcdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTYyNDlcdTMwNmZcdTk1OGJcdTMwNDRcdTMwNjZcdTMwNDRcdTMwOGJcdTcyYjZcdTYxNGJcdTMwNGJcdTMwODlcdTU5Y2JcdTMwODFcdTMwNjZcdWZmMGNcdTkwZThcdTVjNGIgKDEsIDEpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA0Ylx1MzA4OVx1OTBlOFx1NWM0YiAoTSwgTikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDdlXHUzMDY3XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHUzMDZlXHUzMDZiXHU2NzAwXHU3N2VkXHUzMDY3XHU0ZjU1XHU1MjA2XHUzMDRiXHUzMDRiXHUzMDhiXHUzMDRiXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlXHUzMDVmXHUzMDYwXHUzMDU3XHVmZjBjXHU5MGU4XHU1YzRiIChNLCBOKSBcdTMwNmJcdThmYmZcdTMwOGFcdTc3NDBcdTMwNGZcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdTMwNjhcdTMwNGRcdTMwNmZcdTMwNWRcdTMwOGNcdTMwOTJcdTYzMDdcdTY0NThcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTE2NVx1NTI5Ylx1MzA0Ylx1MzA4OVx1NGVlNVx1NGUwYlx1MzA2ZVx1MzBjN1x1MzBmY1x1MzBiZlx1MzA5Mlx1OGFhZFx1MzA3Zlx1OGZiY1x1MzA4MVx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHVmZjBjXHU2NTc0XHU2NTcwIE0sIE4sIEsgXHUzMDRjXHU3YTdhXHU3NjdkXHUzMDkyXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY4XHUzMDU3XHUzMDY2XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlTSBcdTMwNmZcdTVjNGJcdTY1NzdcdTMwNmVcdTY3NzFcdTg5N2ZcdTY1YjlcdTU0MTFcdTMwNmVcdTkwZThcdTVjNGJcdTMwNmVcdTUwMGJcdTY1NzBcdWZmMGNOIFx1MzA2Zlx1NWM0Ylx1NjU3N1x1MzA2ZVx1NTM1N1x1NTMxN1x1NjViOVx1NTQxMVx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NTAwYlx1NjU3MFx1ZmYwY0sgXHUzMDZmXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDZlXHUzMDQyXHUzMDhiXHU5MGU4XHU1YzRiXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvbGk+XHJcblx0PGxpPlx1N2Q5YVx1MzA0ZiBLIFx1ODg0Y1x1MzA2ZVx1MzA0Nlx1MzA2MVx1MzA2ZSBpIFx1ODg0Y1x1NzZlZSAoMSAmbGU7IGkgJmxlOyBLKSBcdTMwNmJcdTMwNmZcdWZmMGNcdTY1NzRcdTY1NzAgWDxzdWI+aTxcL3N1Yj4sIFk8c3ViPmk8XC9zdWI+IFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ZmYwY1x1OTBlOFx1NWM0YiAoWDxzdWI+aTxcL3N1Yj4sIFk8c3ViPmk8XC9zdWI+KSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNmJcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwNGNcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVLIFx1NTAwYlx1MzA2ZVx1N2Q0NCAoWDxzdWI+MTxcL3N1Yj4sIFk8c3ViPjE8XC9zdWI+KSwgKFg8c3ViPjI8XC9zdWI+LCBZPHN1Yj4yPFwvc3ViPiksIC4uLiAsIChYPHN1Yj5LPFwvc3ViPiwgWTxzdWI+SzxcL3N1Yj4pIFx1MzA2Zlx1NGU5Mlx1MzA0NFx1MzA2Ylx1NzU3MFx1MzA2YVx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjIgJmxlOyBNICZsZTsgMTAwIDAwMCBcdTVjNGJcdTY1NzdcdTMwNmVcdTY3NzFcdTg5N2ZcdTY1YjlcdTU0MTFcdTMwNmVcdTkwZThcdTVjNGJcdTMwNmVcdTUwMGJcdTY1NzA8XC9wPlxyXG5cclxuPHA+MiAmbGU7IE4gJmxlOyAxMDAgMDAwIFx1NWM0Ylx1NjU3N1x1MzA2ZVx1NTM1N1x1NTMxN1x1NjViOVx1NTQxMVx1MzA2ZVx1OTBlOFx1NWM0Ylx1MzA2ZVx1NTAwYlx1NjU3MDxcL3A+XHJcblxyXG48cD4xICZsZTsgSyAmbGU7IDIwMCAwMDAgXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDZlXHUzMDQyXHUzMDhiXHU5MGU4XHU1YzRiXHUzMDZlXHU1MDBiXHU2NTcwPFwvcD5cclxuXHJcbjxwPjEgJmxlOyBYaSAmbGU7IE0gXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDZlXHUzMDQyXHUzMDhiXHU5MGU4XHU1YzRiXHUzMDZlXHU2NzcxXHU4OTdmXHU2NWI5XHU1NDExXHUzMDZlXHU0ZjRkXHU3ZjZlPFwvcD5cclxuXHJcbjxwPjEgJmxlOyBZaSAmbGU7IE4gXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDZlXHUzMDQyXHUzMDhiXHU5MGU4XHU1YzRiXHUzMDZlXHU1MzU3XHU1MzE3XHU2NWI5XHU1NDExXHUzMDZlXHU0ZjRkXHU3ZjZlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MWZhXHU1MjliXHUzMDZiXHVmZjBjXHU3OWZiXHU1MmQ1XHUzMDZiXHU2NzAwXHU3N2VkXHUzMDY3XHU0ZjU1XHU1MjA2XHUzMDRiXHUzMDRiXHUzMDhiXHUzMDRiXHUzMDkyXHU4ODY4XHUzMDU5XHU2NTc0XHU2NTcwXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlXHUzMDVmXHUzMDYwXHUzMDU3XHVmZjBjXHU5MGU4XHU1YzRiIChNLCBOKSBcdTMwNmJcdThmYmZcdTMwOGFcdTc3NDBcdTMwNGZcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdTMwNjhcdTMwNGRcdTMwNmZcdTRlZTNcdTMwOGZcdTMwOGFcdTMwNmJcdTY1NzRcdTY1NzAgMSBcdTMwOTJcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiPHA+XHUzMDUzXHUzMDZlXHU0ZjhiXHUzMDY3XHUzMDZmXHVmZjBjXHU0ZWU1XHU0ZTBiXHUzMDZlXHU4ODRjXHU1MmQ1XHUzMDZiXHUzMDg4XHUzMDYzXHUzMDY2IDQgXHU1MjA2XHU5NTkzXHUzMDY3XHU5MGU4XHU1YzRiICgxLCAxKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNGJcdTMwODlcdTkwZThcdTVjNGIgKDMsIDIpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA3OFx1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1ZmYwY1x1MzA1M1x1MzA4Y1x1MzA0Y1x1NjcwMFx1NzdlZFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTkwZThcdTVjNGIgKDEsIDIpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA3OFx1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1ZmYwZTxiciBcLz5cclxuXHU5MGU4XHU1YzRiICgxLCAyKSBcdTMwNmVcdTRlMmRcdTU5MmVcdTMwNmVcdTMwYjlcdTMwYTRcdTMwYzNcdTMwYzFcdTMwOTJcdTYyYmNcdTMwNTlcdWZmMGU8YnIgXC8+XHJcblx1OTBlOFx1NWM0YiAoMiwgMikgXHUzMDZlXHU0ZTJkXHU1OTJlXHUzMDc4XHU3OWZiXHU1MmQ1XHUzMDU5XHUzMDhiXHVmZjBlPGJyIFwvPlxyXG5cdTkwZThcdTVjNGIgKDMsIDIpIFx1MzA2ZVx1NGUyZFx1NTkyZVx1MzA3OFx1NzlmYlx1NTJkNVx1MzA1OVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTMwNTNcdTMwNmVcdTMwNjhcdTMwNGRcdTMwNmVcdTVjNGJcdTY1NzdcdTMwNmVcdTY5ZDhcdTViNTBcdTMwNGNcdTRlZTVcdTRlMGJcdTMwNmVcdTU2ZjNcdTMwNmJcdTg4NjhcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTU2ZjNcdTMwNjdcdTMwNmZcdTUzZjNcdTY1YjlcdTU0MTFcdTMwNGNcdTY3NzFcdWZmMGNcdTRlMGFcdTY1YjlcdTU0MTFcdTMwNGNcdTUzMTdcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGMmdGltZXM7XHU1MzcwXHUzMDZmXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZlXHU0ZjRkXHU3ZjZlXHVmZjBjXHUyNWNiXHU1MzcwXHUzMDZmXHUzMGI5XHUzMGE0XHUzMGMzXHUzMGMxXHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3cucG5nXCIgc3R5bGU9XCJoZWlnaHQ6ODdweDsgd2lkdGg6NjQ3cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==

출처

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