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

문제

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

바이토피아 왕국은 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"를 출력한다. 따옴표는 출력하지 않는다.

서브태스크

번호 배점 제한
1 12

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

2 15

4 ≤ N ≤ 200.

3 23

4 ≤ N ≤ 2 000.

4 50

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

W3sicHJvYmxlbV9pZCI6IjEwMDk4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNTkxXHViZDg0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2RkMTgzZjgzLTZmMmEtNGEyYS04MjljLWRkODVlOGE1NTU1ZVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTE4cHg7IGhlaWdodDogMTg0cHg7IGZsb2F0OiByaWdodDtcIiBcLz5cdWM2MjRcdWI3OWMgXHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4IFx1YmMxNFx1Yzc3NFx1ZDFhMFx1ZDUzY1x1YzU0NCBcdWMxMmNcdWM3NDAgXHViYzE0XHVjNzc0XHVjOWRjXHViOTc0IFx1YzY1NVx1Yzc3NCBcdWIyZTRcdWMyYTRcdWI5YWNcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmMxNFx1Yzc3NFx1YzlkY1x1Yjk3NCBcdWM2NTVcdWM3NTggXHVhYzExXHVjNzkxXHVjMmE0XHViN2ZkXHVhYzhjIFx1YzZiNFx1YmE4NVx1Yzc0NCBcdWIyZWNcdWI5YWNcdWQ1NThcdWM3OTAsIFx1YjQ1MCBcdWM2NTVcdWM3OTAmbmJzcDtcdWJlNDRcdWQxNGNcdWM2MjhcdWFjZmMgXHViYzE0XHVjNzc0XHVkMTRjXHVjNjI4XHVjNzQwJm5ic3A7XHVjNWI0XHViNWJiXHVhYzhjIFx1YzEyY1x1Yzc1OCBcdWI1NDVcdWM3NDQgXHViMDk4XHViMjA0XHVjNWI0IFx1YWMwMFx1YzgzOFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzBcdWI4NWMgXHVjMmY4XHVjNmIwXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWI1NDVcdWM3NDQgXHViNDUwIFx1YWMxY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHVjODEwXHViODM5XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzE0XHVjNzc0XHVkMWEwXHVkNTNjXHVjNTQ0IFx1YzY1NVx1YWQ2ZFx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJjYzBcdWM3NDAgXHVjOWMwXHViM2M0XHVjNzU4IFx1ZDU1YyBcdWJjYzBcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHViYTcwLCAmbmJzcDtcdWJhYThcdWI0ZTAgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YjQ1MCBcdWJjYzBcdWM3NDAgXHVjMTFjXHViODVjIFx1YzIxOFx1YzljMVx1ZDU1OFx1YjJlNC4gXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmQ5OVx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViNDUwIFx1YmNjMFx1Yzc0MCZuYnNwO1x1YjBiNFx1YmQ4MFx1YzVkMFx1YzExYyBcdWM4MDhcdWIzMDAgXHViOWNjXHViMDk4XHVhYzcwXHViMDk4IFx1YjJlNFx1Yjk3OCBcdWJjYzBcdWM3NDQgXHVhYzc0XHViNGRjXHViOWFjXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZTQ0XHVkMTRjXHVjNjI4XHVhY2ZjIFx1YmMxNFx1Yzc3NFx1ZDE0Y1x1YzYyOCBcdWM2NTVcdWM3OTBcdWIyOTQgXHVjNzc0IFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHViNTQ1XHVjNzQ0IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWQ1NWMgXHViY2MwXHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1YyBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2JkXHVhY2M0XHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyZuYnNwO1x1YjQ1MCBcdWFjMWNcdWM3NTggXHVkNTY5XHViM2Q5XHVjNzc4IFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWI4MjQgXHVkNTVjXHViMmU0LiAoXHViNDUwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWIzY2NcdWI5YWNcdWFjNzBcdWIwOTggXHViNGE0XHVjOWQxXHVjNWI0XHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWJhYThcdWM1OTFcdWM3NzQgXHViNDE4XHViYTc0IFx1ZDU2OVx1YjNkOVx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQpIFx1YWNiZFx1YWNjNFx1YzEyMFx1Yzc1OCBcdWM1OTFcdWIwNWRcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzgxNVx1YzIxOFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjdmMCBcdWFjYmRcdWFjYzRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWNlMCwgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1YWNiZFx1YWNjNFx1YzEyMFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjYzNlXHVjNTQ0XHViMGI0XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWMxMmNcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVhZGY4IFx1YjRhNFx1Yzc1OCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiZuYnNwOygwICZsZTsgWDxzdWI+aTxcL3N1Yj4sIFk8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KSBcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5ODksIFx1YzEyY1x1Yzc0MCZuYnNwOyhYPHN1Yj4xPFwvc3ViPiwgWTxzdWI+MTxcL3N1Yj4pICZtaW51czsgKFg8c3ViPjI8XC9zdWI+LCBZPHN1Yj4yPFwvc3ViPiksIChYPHN1Yj4yPFwvc3ViPiwgWTxzdWI+MjxcL3N1Yj4pICZtaW51czsgKFg8c3ViPjM8XC9zdWI+LCBZPHN1Yj4zPFwvc3ViPiksIC4uLiZuYnNwOywgKFg8c3ViPk4mbWludXM7MTxcL3N1Yj4sIFk8c3ViPk4mbWludXM7MTxcL3N1Yj4pICZtaW51czsgKFg8c3ViPk48XC9zdWI+LCBZPHN1Yj5OPFwvc3ViPiksIChYPHN1Yj5OPFwvc3ViPiwgWTxzdWI+TjxcL3N1Yj4pICZtaW51czsgKFg8c3ViPjE8XC9zdWI+LCBZPHN1Yj4xPFwvc3ViPilcdWM3NTggXHVjMTIwXHViZDg0XHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3MDRcdWM1ZDBcdWIzYzQgXHVjNWI4XHVhZTA5XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzljMFx1YjljYyBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHViNDUwIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWM1YjhcdWM4MWNcdWIwOTggXHVjMTFjXHViODVjIFx1YzIxOFx1YzljMVx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMxMmNcdWM3NDQgXHVkNTY5XHViM2Q5XHVjNzc4IFx1YjQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQsIFx1YzEyMFx1YmQ4NFx1Yzc1OCZuYnNwO1x1YjQ1MCBcdWIwNWRcdWM4MTBcdWM3NzQmbmJzcDsoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSwmbmJzcDsoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KVx1Yzc3YyBcdWI1NGMmbmJzcDt4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4sJm5ic3A7eDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCA0XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwJm5ic3A7XHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4geDxzdWI+MTxcL3N1Yj4mbmJzcDs9IHg8c3ViPjI8XC9zdWI+XHVjNzc0XHVhYzcwXHViMDk4IHk8c3ViPjE8XC9zdWI+Jm5ic3A7PSB5PHN1Yj4yPFwvc3ViPlx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVjNTQ4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjODEwXHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjYmRcdWFjYzRcdWMxMjBcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwIFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NzRcdWJhNzQgXHVhZGY4IFx1YzkxMVx1YzVkMCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+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

채점 및 기타 정보

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