{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eA \u003ci\u003etriangulation\u003c/i\u003e of a polygon \u003ci\u003eP\u003c/i\u003e is its partition into non-overlapping triangles whose union is \u003ci\u003eP\u003c/i\u003e. In this problem, we put some restrictions on triangulations: all vertices of a triangle must coincide with some vertices of \u003ci\u003eP\u003c/i\u003e and no vertex of \u003ci\u003eP\u003c/i\u003e must lie on a boundary of a triangle (except for triangle\u0027s vertices). We call a segment \u003ci\u003einterfering\u003c/i\u003e with a triangulation if it intersects (or touches) a boundary of some triangle of the triangulation.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eYour task is, given the polygon \u003ci\u003eP\u003c/i\u003e and segment \u003ci\u003eS\u003c/i\u003e, to determine whether there exists a triangulation that \u003ci\u003eS\u003c/i\u003e does not interfere with. Since it is well-known that all simple polygons can be triangulated, you have only to output the triangle that belongs to some triangulation and contains \u003ci\u003eS\u003c/i\u003e strictly inside.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIn the first line there is \u003ci\u003eN\u003c/i\u003e \u003cnobr\u003e(3 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 800)\u003c/nobr\u003e\u0026nbsp;— the number of vertices in \u003ci\u003eP\u003c/i\u003e.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe following \u003ci\u003eN\u003c/i\u003e lines contain pairs of integers (\u003ci\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e,\u0026nbsp;\u003ci\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e)\u0026nbsp;— the coordinates of vertices of \u003ci\u003eP\u003c/i\u003e in the order of traversal. All points are distinct, and no three consecutive points lie on the same line.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe last line contain four integers \u003ci\u003eX\u003csub\u003es\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eY\u003csub\u003es\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eX\u003csub\u003ef\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eY\u003csub\u003ef\u003c/sub\u003e\u003c/i\u003e\u0026nbsp;— the coordinates of endpoints of \u003ci\u003eS\u003c/i\u003e.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAll coordinates do not exceed 10\u003csup\u003e4\u003c/sup\u003e by absolute value. The segment \u003ci\u003eS\u003c/i\u003e is guaranteed to lie strictly inside the polygon \u003ci\u003eP\u003c/i\u003e. \u003ci\u003eS\u003c/i\u003e is also guaranteed to have non-zero length.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf the solution does exist, output the one-based indices of vertices of triangle that belongs to some triangulation and contains \u003ci\u003eS\u003c/i\u003e strictly inside. The indices must be output in a single line and separated by single spaces.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf the solution does not exist, output the word \"Impossible\" in a single line.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","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\u003e3\r\n0 0\r\n0 3\r\n4 3\r\n1 2 2 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\u003e4\r\n0 0\r\n2 0\r\n2 3\r\n0 3\r\n1 1 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eImpossible\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}