{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eNo Great Victory anniversary in Berland has ever passed without the war parade. This year is not an exception. That’s why the preparations are on in full strength. Tanks are building a line, artillery mounts are ready to fire, soldiers are marching on the main square... And the air forces general Mr. Generalov is in trouble again. This year a lot of sky-scrapers have been built which makes it difficult for the airplanes to fly above the city. It was decided that the planes should fly strictly from south to north. Moreover, there must be no sky scraper on a plane’s route, otherwise the anniversary will become a tragedy. The Ministry of Building gave the data on \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e sky scrapers (the rest of the buildings are rather small and will not be a problem to the planes). When looking at the city from south to north as a geometrical plane, the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th building is a rectangle of height \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Its westernmost point has the x-coordinate of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and the easternmost — of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. The terrain of the area is plain so that all the buildings stand on one level. Your task as the Ministry of Defence’s head programmer is to find an \u003cspan class\u003d\"tex-font-style-it\"\u003eenveloping\u003c/span\u003e polyline using the data on the sky-scrapers. The polyline’s properties are as follows:\u003c/p\u003e\u003cul\u003e \u003cli\u003e If you look at the city from south to north as a plane, then any part of any building will be inside or on the boarder of the area that the polyline encloses together with the land surface. \u003c/li\u003e\u003cli\u003e The polyline starts and ends on the land level, i.e. at the height equal to 0. \u003c/li\u003e\u003cli\u003e The segments of the polyline are parallel to the coordinate axes, i.e. they can only be vertical or horizontal. \u003c/li\u003e\u003cli\u003e The polyline’s vertices should have integer coordinates. \u003c/li\u003e\u003cli\u003e If you look at the city from south to north the polyline (together with the land surface) must enclose the minimum possible area. \u003c/li\u003e\u003cli\u003e The polyline must have the smallest length among all the polylines, enclosing the minimum possible area with the land. \u003c/li\u003e\u003cli\u003e The consecutive segments of the polyline must be perpendicular. \u003c/li\u003e\u003c/ul\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" height\u003d\"151px\" src\u003d\"CDN_BASE_URL/7b0a3eebdfef389cf5389587fc895a18?v\u003d1726332978\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"680px\"\u003e \u003c/center\u003e\u003ccenter\u003e Picture to the second sample test (the enveloping polyline is marked on the right). \u003c/center\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first input line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100000\u003c/span\u003e). Then follow \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines, each containing three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, - 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e ≤ \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIn the first line output integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e — amount of vertices of the enveloping polyline. The next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines should contain 2 integers each — the position and the height of the polyline’s vertex. Output the coordinates of each vertex in the order of traversing the polyline from west to east. Remember that the first and the last vertices of the polyline should have the height of 0.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 0 2\n4 1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n0 0\n0 3\n1 3\n1 4\n3 4\n3 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n3 -3 0\n2 -1 1\n4 2 4\n2 3 7\n3 6 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\n-3 0\n-3 3\n0 3\n0 2\n1 2\n1 0\n2 0\n2 4\n4 4\n4 2\n6 2\n6 3\n8 3\n8 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}