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

문제

오랜 시간동안 바이토피아 섬은 바이짜르 왕이 다스리고 있었다. 하지만, 바이짜르 왕의 갑작스럽게 운명을 달리하자, 두 왕자 비테온과 바이테온은 어떻게 섬의 땅을 나누어 가져야 하는지로 싸우게 되었다. 결국 그들은 땅을 두 개로 나누어 점령하기로 하였다.

바이토피아 왕국은 N개의 꼭짓점이 있는 다각형의 모양이다. 다각형의 모든 변은 지도의 한 변에 평행하며, 모든 붙어있는 두 변은 서로 수직하다. 다각형의 붙어있지 않은 두 변은 내부에서 절대 만나거나 다른 변을 건드리지 않는다.

비테온과 바이테온 왕자는 이 다각형 모양의 땅을 지도의 한 변에 평행한 하나의 경계선을 이용하여 두 개의 합동인 다각형으로 나누려 한다. (두 다각형이 돌리거나 뒤집어서 같은 모양이 되면 합동이라 한다) 경계선의 양끝의 좌표는 정수여야 한다.

이런 경계선이 존재하는지를 확인하고, 존재한다면 경계선을 하나 찾아내시오.

입력

입력의 첫 줄에는 다각형 모양의 섬을 이루는 꼭짓점의 개수 N이 주어진다. 그 뒤의 N개의 줄에는 정점의 좌표 Xi, Yi (0 ≤ Xi, Yi ≤ 109) 가 순서대로 주어진다.

즉, 섬은 (X1, Y1) − (X2, Y2), (X2, Y2) − (X3, Y3), ... , (XN−1, YN−1) − (XN, YN), (XN, YN) − (X1, Y1)의 선분들로 이루어져 있는 것이다. 위에도 언급되어 있지만 붙어있는 두 선분은 언제나 서로 수직하다.

출력

섬을 합동인 두 다각형으로 나누는 선분이 존재하면, 선분의 두 끝점이 (x1, y1), (x2, y2)일 때 x1, y1, x2, y2를 나타내는 4개의 정수를 한 줄에 출력하면 된다. x1 = x2이거나 y1 = y2여야 한다. 선분은 다각형의 안쪽에 있어야 하며, 선분의 양 끝점은 다각형의 경계선에 있어야 한다. 그런 선분이 여러개이면 그 중에 하나를 출력한다.

그런 선분이 존재하지 않으면, "NO"를 출력한다. 따옴표는 출력하지 않는다.

서브태스크

번호배점제한
112

4 ≤ N ≤ 100 000. 어떠한 수직선 혹은 수평선으로 다각형을 잘랐을 때, 다각형은 정확히 두 조각으로 분할된다.

215

4 ≤ N ≤ 200.

323

4 ≤ N ≤ 2 000.

450

4 ≤ N ≤ 100 000.

예제 입력 1

10
0 0
1 0
1 1
3 1
3 5
2 5
2 3
1 3
1 2
0 2

예제 출력 1

1 2 3 2

예제 입력 2

6
0 0
1 0
1 1
2 1
2 2
0 2

예제 출력 2

NO

W3sicHJvYmxlbV9pZCI6IjEwMDk4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNTkxXHViZDg0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2RkMTgzZjgzLTZmMmEtNGEyYS04MjljLWRkODVlOGE1NTU1ZVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTE4cHg7IGhlaWdodDogMTg0cHg7IGZsb2F0OiByaWdodDtcIiBcLz5cdWM2MjRcdWI3OWMgXHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4IFx1YmMxNFx1Yzc3NFx1ZDFhMFx1ZDUzY1x1YzU0NCBcdWMxMmNcdWM3NDAgXHViYzE0XHVjNzc0XHVjOWRjXHViOTc0IFx1YzY1NVx1Yzc3NCBcdWIyZTRcdWMyYTRcdWI5YWNcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmMxNFx1Yzc3NFx1YzlkY1x1Yjk3NCBcdWM2NTVcdWM3NTggXHVhYzExXHVjNzkxXHVjMmE0XHViN2ZkXHVhYzhjIFx1YzZiNFx1YmE4NVx1Yzc0NCBcdWIyZWNcdWI5YWNcdWQ1NThcdWM3OTAsIFx1YjQ1MCBcdWM2NTVcdWM3OTAgXHViZTQ0XHVkMTRjXHVjNjI4XHVhY2ZjIFx1YmMxNFx1Yzc3NFx1ZDE0Y1x1YzYyOFx1Yzc0MCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjMTJjXHVjNzU4IFx1YjU0NVx1Yzc0NCBcdWIwOThcdWIyMDRcdWM1YjQgXHVhYzAwXHVjODM4XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjg1YyBcdWMyZjhcdWM2YjBcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFjYjBcdWFkNmQgXHVhZGY4XHViNGU0XHVjNzQwIFx1YjU0NVx1Yzc0NCBcdWI0NTAgXHVhYzFjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4MTBcdWI4MzlcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMTRcdWM3NzRcdWQxYTBcdWQ1M2NcdWM1NDQgXHVjNjU1XHVhZDZkXHVjNzQwIE5cdWFjMWNcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViYWE4XHVjNTkxXHVjNzc0XHViMmU0LiBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViYWE4XHViNGUwIFx1YmNjMFx1Yzc0MCBcdWM5YzBcdWIzYzRcdWM3NTggXHVkNTVjIFx1YmNjMFx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWJhNzAsICBcdWJhYThcdWI0ZTAgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YjQ1MCBcdWJjYzBcdWM3NDAgXHVjMTFjXHViODVjIFx1YzIxOFx1YzljMVx1ZDU1OFx1YjJlNC4gXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmQ5OVx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViNDUwIFx1YmNjMFx1Yzc0MCBcdWIwYjRcdWJkODBcdWM1ZDBcdWMxMWMgXHVjODA4XHViMzAwIFx1YjljY1x1YjA5OFx1YWM3MFx1YjA5OCBcdWIyZTRcdWI5NzggXHViY2MwXHVjNzQ0IFx1YWM3NFx1YjRkY1x1YjlhY1x1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmU0NFx1ZDE0Y1x1YzYyOFx1YWNmYyBcdWJjMTRcdWM3NzRcdWQxNGNcdWM2MjggXHVjNjU1XHVjNzkwXHViMjk0IFx1Yzc3NCBcdWIyZTRcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1YjU0NVx1Yzc0NCBcdWM5YzBcdWIzYzRcdWM3NTggXHVkNTVjIFx1YmNjMFx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNiZFx1YWNjNFx1YzEyMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWQ1NjlcdWIzZDlcdWM3NzggXHViMmU0XHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YjgyNCBcdWQ1NWNcdWIyZTQuIChcdWI0NTAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YjNjY1x1YjlhY1x1YWM3MFx1YjA5OCBcdWI0YTRcdWM5ZDFcdWM1YjRcdWMxMWMgXHVhYzE5XHVjNzQwIFx1YmFhOFx1YzU5MVx1Yzc3NCBcdWI0MThcdWJhNzQgXHVkNTY5XHViM2Q5XHVjNzc0XHViNzdjIFx1ZDU1Y1x1YjJlNCkgXHVhY2JkXHVhY2M0XHVjMTIwXHVjNzU4IFx1YzU5MVx1YjA1ZFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjODE1XHVjMjE4XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2YwIFx1YWNiZFx1YWNjNFx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTU4XHVhY2UwLCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhY2JkXHVhY2M0XHVjMTIwXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNjM2VcdWM1NDRcdWIwYjRcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1YzEyY1x1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjRhNFx1Yzc1OCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVjMTJjXHVjNzQwIChYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pICZtaW51czsgKFg8c3ViPjI8XC9zdWI+LCBZPHN1Yj4yPFwvc3ViPiksIChYPHN1Yj4yPFwvc3ViPiwgWTxzdWI+MjxcL3N1Yj4pICZtaW51czsgKFg8c3ViPjM8XC9zdWI+LCBZPHN1Yj4zPFwvc3ViPiksIC4uLiAsIChYPHN1Yj5OJm1pbnVzOzE8XC9zdWI+LCBZPHN1Yj5OJm1pbnVzOzE8XC9zdWI+KSAmbWludXM7IChYPHN1Yj5OPFwvc3ViPiwgWTxzdWI+TjxcL3N1Yj4pLCAoWDxzdWI+TjxcL3N1Yj4sIFk8c3ViPk48XC9zdWI+KSAmbWludXM7IChYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pXHVjNzU4IFx1YzEyMFx1YmQ4NFx1YjRlNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzA0XHVjNWQwXHViM2M0IFx1YzViOFx1YWUwOVx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YjQ1MCBcdWMxMjBcdWJkODRcdWM3NDAgXHVjNWI4XHVjODFjXHViMDk4IFx1YzExY1x1Yjg1YyBcdWMyMThcdWM5YzFcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMTJjXHVjNzQ0IFx1ZDU2OVx1YjNkOVx1Yzc3OCBcdWI0NTAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0LCBcdWMxMjBcdWJkODRcdWM3NTggXHViNDUwIFx1YjA1ZFx1YzgxMFx1Yzc3NCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSwgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPilcdWM3N2MgXHViNTRjIHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCA0XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIHg8c3ViPjE8XC9zdWI+ID0geDxzdWI+MjxcL3N1Yj5cdWM3NzRcdWFjNzBcdWIwOTggeTxzdWI+MTxcL3N1Yj4gPSB5PHN1Yj4yPFwvc3ViPlx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVjNTQ4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjODEwXHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjYmRcdWFjYzRcdWMxMjBcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwIFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NzRcdWJhNzQgXHVhZGY4IFx1YzkxMVx1YzVkMCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZjAgXHVjMTIwXHViZDg0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQsICZxdW90O05PJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHVjNjM0XHVkNDVjXHViMjk0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic3VidGFzazEiOiI8cD40ICZsZTsgTiAmbGU7IDEwMCAwMDAuIFx1YzViNFx1YjVhMFx1ZDU1YyBcdWMyMThcdWM5YzFcdWMxMjAgXHVkNjM5XHVjNzQwIFx1YzIxOFx1ZDNjOVx1YzEyMFx1YzczY1x1Yjg1YyBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzk4XHViNzkwXHVjNzQ0IFx1YjU0YywgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWI0NTAgXHVjODcwXHVhYzAxXHVjNzNjXHViODVjIFx1YmQ4NFx1ZDU2MFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPjQgJmxlOyBOICZsZTsgMjAwLjxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+NCAmbGU7IE4gJmxlOyAyIDAwMC48XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPjQgJmxlOyBOICZsZTsgMTAwIDAwMC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9jNTRkZDEzOC1lNTY0LTQwNmMtYTY3NC0zZDQ3ZTJkM2IwYzlcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDEyMnB4OyBoZWlnaHQ6IDE5OHB4O1wiIFwvPjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2E3OGQ0ODdiLWIwYmMtNGRhMC05Mzc1LTc3NGM1NTM2NjRiOFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogODNweDsgaGVpZ2h0OiA4NXB4O1wiIFwvPjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjEwMDk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGVtYXJjYXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZGQxODNmODMtNmYyYS00YTJhLTgyOWMtZGQ4NWU4YTU1NTVlXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxMThweDsgaGVpZ2h0OiAxODRweDsgZmxvYXQ6IHJpZ2h0O1wiIFwvPkZvciBhIGxvbmcgdGltZSB0aGUgaXNsYW5kIG9mIEJ5dG9waWEgd2FzIHJ1bGVkIGJ5IHRoZSBmYWlyIGtpbmcgQnl0ZWFzYXIuIEJ1dCBhZnRlciB0aGUgc3VkZGVuIGRlYXRoIG9mIHRoZSBraW5nLCBoaXMgdHdvIHNvbnMmbWRhc2g7dHdpbnMgQml0ZW9uIGFuZCBCeXRlb24mbWRhc2g7Y291bGQgbm90IGNvbWUgdG8gYW4gYWdyZWVtZW50IHdoaWNoIG9uZSBvZiB0aGVtIHNob3VsZCBhc2NlbmQgdGhlIHRocm9uZS4gVGhlcmVmb3JlIHRoZXkgZGVjaWRlZCB0byBkaXZpZGUgdGhlIGlzbGFuZCBpbnRvIHR3byBwcm92aW5jZXMgdG8gcnVsZSB0aGVtIGluZGVwZW5kZW50bHkuPFwvcD5cclxuXHJcbjxwPk9uIGEgcmVjdGFuZ3VsYXIgbWFwIEJ5dGVvdGlhIGlzIHNoYXBlZCBhcyBhIHBvbHlnb24gb2YgTiB2ZXJ0aWNlcy4gRXZlcnkgc2lkZSBvZiB0aGUgcG9seWdvbiBpcyBwYXJhbGxlbCB0byBhIHNpZGUgb2YgdGhlIG1hcCwgYW5kIGV2ZXJ5IHR3byBjb25zZWN1dGl2ZSBzaWRlcyBhcmUgcGVycGVuZGljdWxhciB0byBlYWNoIG90aGVyLiBObyBzaWRlIG9mIHRoZSBwb2x5Z29uIGNyb3NzZXMgb3IgdG91Y2hlcyBhbnkgb3RoZXIgc2lkZSwgZXhjZXB0IGZvciB0aGUgY29tbW9uIGVuZHBvaW50cyBvZiBjb25zZWN1dGl2ZSBzaWRlcy48XC9wPlxyXG5cclxuPHA+Qml0ZW9uIGFuZCBCeXRlb24gd2FudCB0byBkaXZpZGUgdGhlIHBvbHlnb24gaW50byB0d28gY29uZ3J1ZW50IHBvbHlnb25zLCB1c2luZyBvbmUgbGluZSBzZWdtZW50IGNvbnRhaW5lZCBpbiB0aGUgcG9seWdvbiBhbmQgcGFyYWxsZWwgdG8gYSBzaWRlIG9mIHRoZSBtYXAuIChUd28gcG9seWdvbnMgYXJlIGNvbmdydWVudCBpZiBvbmUgY2FuIGJlIHRyYW5zZm9ybWVkIGludG8gdGhlIG90aGVyIHVzaW5nIGEgY29tYmluYXRpb24gb2YgcmVmbGVjdGlvbnMsIHJvdGF0aW9ucyBhbmQgdHJhbnNsYXRpb25zLikgQ29vcmRpbmF0ZXMgb2YgdGhlIHBvbHlnb24gdmVydGljZXMgYW5kIHRoZSBlbmRwb2ludHMgb2YgdGhlIGRpdmlkaW5nIHNlZ21lbnQgYXJlIGludGVnZXJzLjxcL3A+XHJcblxyXG48cD5UaGUga2luZyZyc3F1bztzIHNvbnMgYXNrZWQgeW91IHRvIHZlcmlmeSB3aGV0aGVyIHN1Y2ggYSBkaXZpc2lvbiBpcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHNoYXBlIG9mIHRoZSBpc2xhbmQsIGRldGVybWluZSBpZiBpdCBjYW4gYmUgcGFydGl0aW9uZWQgYnkgYSBob3Jpem9udGFsIG9yIHZlcnRpY2FsIHNlZ21lbnQgaW50byB0d28gY29uZ3J1ZW50IHBpZWNlcy4gSWYgaXQgY2FuLCBmaW5kIG9uZSBzdWNoIHNlZ21lbnQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOLCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzLiBUaGUgaXRoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgYSBwYWlyIG9mIGludGVnZXJzIFg8c3ViPmk8XC9zdWI+IGFuZCBZPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikgd2hpY2ggYXJlIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgaXRoIHZlcnRleC48XC9wPlxyXG5cclxuPHA+VGhlIHZlcnRpY2VzIGFyZSBnaXZlbiBpbiBvcmRlciwgaS5lLiB0aGUgbGluZSBzZWdtZW50cyAoWDxzdWI+MTxcL3N1Yj4sIFk8c3ViPjE8XC9zdWI+KSAmbWludXM7IChYPHN1Yj4yPFwvc3ViPiwgWTxzdWI+MjxcL3N1Yj4pLCAoWDxzdWI+MjxcL3N1Yj4sIFk8c3ViPjI8XC9zdWI+KSAmbWludXM7IChYPHN1Yj4zPFwvc3ViPiwgWTxzdWI+MzxcL3N1Yj4pLCAuIC4gLiAsIChYPHN1Yj5OJm1pbnVzOzE8XC9zdWI+LCBZPHN1Yj5OJm1pbnVzOzE8XC9zdWI+KSAmbWludXM7IChYPHN1Yj5OPFwvc3ViPiwgWTxzdWI+TjxcL3N1Yj4pIGFuZCAoWDxzdWI+TjxcL3N1Yj4sIFk8c3ViPk48XC9zdWI+KSAmbWludXM7IChYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pIGFyZSBhbGwgc2lkZXMgb2YgdGhlIHBvbHlnb24uIEZ1cnRoZXJtb3JlLCBhbnkgdHdvIGNvbnNlY3V0aXZlIGxpbmUgc2VnbWVudHMgYXJlIHBlcnBlbmRpY3VsYXIgdG8gZWFjaCBvdGhlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBhIHNpbmdsZSBsaW5lLiBJZiBpdCBpcyBwb3NzaWJsZSB0byBkaXZpZGUgdGhlIGlzbGFuZCBpbnRvIGNvbmdydWVudCBwYXJ0cyB3aXRoIGEgaG9yaXpvbnRhbCBvciB2ZXJ0aWNhbCBzZWdtZW50IHdpdGggZW5kcG9pbnRzICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pIGFuZCAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KSwgcHJpbnQgNCBpbnRlZ2VycyB4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+IGFuZCB5PHN1Yj4yPFwvc3ViPiwgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gRWl0aGVyIHg8c3ViPjE8XC9zdWI+ID0geDxzdWI+MjxcL3N1Yj4gb3IgeTxzdWI+MTxcL3N1Yj4gPSB5PHN1Yj4yPFwvc3ViPiBtdXN0IGhvbGQuIFRoZSBzZWdtZW50IHNob3VsZCBiZSBjb250YWluZWQgd2l0aGluIHRoZSBwb2x5Z29uIGFuZCBvbmx5IGl0cyBlbmRwb2ludHMgc2hvdWxkIHRvdWNoIHRoZSBib3VuZGFyeS48XC9wPlxyXG5cclxuPHA+SWYgYSBzdWl0YWJsZSBkaXZpc2lvbiBjYW5ub3QgYmUgZm91bmQsIG91dHB1dCBhIHNpbmdsZSB3b3JkIDxjb2RlPk5PPFwvY29kZT4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInN1YnRhc2sxIjoiPHA+NCAmbGU7IE4gJmxlOyAxMDAgMDAwLiBBbnkgaG9yaXpvbnRhbCBvciB2ZXJ0aWNhbCBsaW5lIHRoYXQgZGl2aWRlcyB0aGUgcG9seWdvbiBkaXZpZGVzIGl0IGludG8gZXhhY3RseSB0d28gcGFydHMuPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD40ICZsZTsgTiAmbGU7IDIwMC48XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPjQgJmxlOyBOICZsZTsgMiAwMDAuPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD40ICZsZTsgTiAmbGU7IDEwMCAwMDAuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPk5vdGUgdGhhdCA8Y29kZT4zIDIgMSAyPFwvY29kZT4gaXMgYWxzbyBhIHZhbGlkIHNvbHV0aW9uLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2M1NGRkMTM4LWU1NjQtNDA2Yy1hNjc0LTNkNDdlMmQzYjBjOVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTIycHg7IGhlaWdodDogMTk4cHg7XCIgXC8+PFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPkluIHRoaXMgY2FzZSB0aGVyZSBpcyBubyB3YXkgdG8gZGl2aWRlIHRoZSBpc2xhbmQgaW50byB0d28gY29uZ3J1ZW50IHBhcnRzLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2E3OGQ0ODdiLWIwYmMtNGRhMC05Mzc1LTc3NGM1NTM2NjRiOFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogODNweDsgaGVpZ2h0OiA4NXB4O1wiIFwvPjxcL3A+XHJcbiJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2014 4번

  • 문제를 번역한 사람: junie

채점 및 기타 정보

  • 예제는 채점하지 않는다.