{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nAlice comes up with a new game and wants to play with Bob.\n\u003c/p\u003e\n\u003cp\u003e\nThere is one rectangle on the paper initially, we define its lower-left corner\u0027s coordinate is (x\u003csub\u003eL\u003c/sub\u003e, y\u003csub\u003eL\u003c/sub\u003e) and upper-right corner\u0027s coordinate is (x\u003csub\u003eR\u003c/sub\u003e, y\u003csub\u003eR\u003c/sub\u003e).\n\u003c/p\u003e\n\u003cp\u003e\nBob has executed the step as description below N times:\n\u003c/p\u003e\n\u003cp\u003e\nBob should select one empty rectangle. If the rectangle is the initial one or is split by one vertical segment, he should split it into two parts by drawing one horizontal segment; otherwise he should split the rectangle into two parts by drawing one vertical segment. An empty rectangle means there is no segment in this rectangle except its only four boundary segments.\n\u003c/p\u003e\n\u003cp\u003e\nYou should pay attention that there are only two kinds segments: vertical segment and horizontal segment.\n\u003c/p\u003e\n\u003cp\u003e\nNow Bob has several queries. In each query, Bob selects two target points in the paper. (You can assume that all given target points are always located inside the initial rectangle and not in any drawing segments.) He wants Alice to answer the question as soon as possible: Alice can erase several existing segments, and make two target points in one empty rectangle, and she should answer how many empty rectangles at most would be left at last.\n\u003c/p\u003e\n\u003cp\u003e\nBut there are some restrictions: Alice cannot erase segments of the initial rectangle (the (x\u003csub\u003eL\u003c/sub\u003e, y\u003csub\u003eL\u003c/sub\u003e) to (x\u003csub\u003eR\u003c/sub\u003e, y\u003csub\u003eR\u003c/sub\u003e) one), she can only erase segments drew by Bob; if Alice want to erase one segment, both sides of the segment must be empty rectangles, and after erase it, the two empty rectangles must combine to one bigger empty rectangle; if erasing an existing segment will lead to a disconnected graph, the operation is forbidden.\n\u003c/p\u003e\n\u003cdiv style\u003d\"text-align: center;\"\u003e\n\t\u003cimg src\u003d\"CDN_BASE_URL/d76dc0358f18f48a0db0316e9ea4d446?v\u003d1726373035\"\u003e\n\u003c/div\u003e\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003e\nThere are multiple test cases.\n\u003c/p\u003e\n\u003cp\u003e\nThe first line contains four integers x\u003csub\u003eL\u003c/sub\u003e, y\u003csub\u003eL\u003c/sub\u003e, x\u003csub\u003eR\u003c/sub\u003e, y\u003csub\u003eR\u003c/sub\u003e indicating the coordinates of the lower-left corner and the upper-right corner of the initial huge rectangle respectively. (-100,000 ≤ x\u003csub\u003eL\u003c/sub\u003e, y\u003csub\u003eL\u003c/sub\u003e, x\u003csub\u003eR\u003c/sub\u003e, y\u003csub\u003eR\u003c/sub\u003e ≤ 100,000, x\u003csub\u003eL\u003c/sub\u003e\u0026lt; x\u003csub\u003eR\u003c/sub\u003e, y\u003csub\u003eL\u003c/sub\u003e\u0026lt; y\u003csub\u003eR\u003c/sub\u003e)\n\u003c/p\u003e\n\u003cp\u003e\nThe next line contains two integers N and Q. (1 ≤ N, Q ≤ 1000)\n\u003c/p\u003e\n\u003cp\u003e\nThe next N lines each line contains four integers x\u003csub\u003e1\u003c/sub\u003e, y\u003csub\u003e1\u003c/sub\u003e, x\u003csub\u003e2\u003c/sub\u003e, y\u003csub\u003e2\u003c/sub\u003e indicating the coordinates of two endpoints of one drawing segments. (-100,000 ≤ x\u003csub\u003e1\u003c/sub\u003e, y\u003csub\u003e1\u003c/sub\u003e, x\u003csub\u003e2\u003c/sub\u003e, y\u003csub\u003e2\u003c/sub\u003e ≤ 100,000, x\u003csub\u003e1\u003c/sub\u003e\u003dx\u003csub\u003e2\u003c/sub\u003e|y\u003csub\u003e1\u003c/sub\u003e\u003dy\u003csub\u003e2\u003c/sub\u003e)\n\u003c/p\u003e\n\u003cp\u003e\nThe next Q lines each line contains four integers x\u003csub\u003eA\u003c/sub\u003e, y\u003csub\u003eA\u003c/sub\u003e, x\u003csub\u003eB\u003c/sub\u003e, y\u003csub\u003eB\u003c/sub\u003e indicating the coordinates of two target points in this query. (-100,000 ≤ x\u003csub\u003eA\u003c/sub\u003e, y\u003csub\u003eA\u003c/sub\u003e, x\u003csub\u003eB\u003c/sub\u003e, y\u003csub\u003eB\u003c/sub\u003e ≤ 100,000).\n\u003c/p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003e\nFor each test case, output Q lines, output the answer of each query in each line.\n\u003c/p\u003e\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e-10 -10 10 10\n5 1\n-10 0 10 0\n5 -10 5 0\n-5 0 -5 10\n-5 5 10 5\n5 -5 10 -5\n0 -3 7 -3\n0 0 4 4\n3 2\n0 2 4 2\n2 0 2 2\n2 2 2 4\n1 1 1 3\n1 1 3 1\n-10 -10 10 10\n3 4\n-10 0 10 0\n0 -10 0 0\n0 0 0 10\n-9 -9 -8 -8\n-9 -9 -9 9\n-9 -9 9 -9\n-9 -9 9 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1\n3\n4\n1\n3\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}