{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Biaoge is planning to walk to amusement park. The city he lives can be abstracted as a 2D plane. Biaoge is at (x1, y1) and the amusement park is at (x2, y2). There are also some rectangle buildings. Biaoge can only walk parallel to the coordinate axis. Of course Biaoge can’t walk across the buildings.\u003cbr\u003e What’s the minimum number of turns Biaoge need to make?\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/06aabc9b4ea594bc8d6e998d1e6f4d7a?v\u003d1726439684\"\u003e\u003c/center\u003e\u003cbr\u003e As the figure above shows, there are 4 buildings and Biaoge need to make at least 3 turns to reach the amusement park(Before walking he can chose a direction freely). It is guaranteed that all the buildings are parallel to the coordination axis. Buildings may contact but overlapping is impossible. The amusement park and Biaoge’s initial positions will not contact or inside any building.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" There are multiple test case.\u003cbr\u003e Each test case contains several lines.\u003cbr\u003e The first line contains 4 integers x1, y1, x2, y2 indicating the coordinate of Biaoge and amusement park.\u003cbr\u003e The second line contains one integer N(0≤N≤50), indicating the number of buildings.\u003cbr\u003e Then N lines follows, each contains 4 integer x1, y1, x2, y2, indicating the coordinates of two opposite vertices of the building.\u003cbr\u003e Input ends with 0 0 0 0, you should not process it.\u003cbr\u003e All numbers in the input range from -10\u003csup\u003e8\u003c/sup\u003e to 10\u003csup\u003e8\u003c/sup\u003e."}},{"title":"Output","value":{"format":"HTML","content":" For each test case, output the number of least turns in a single line. If Biaoge can’t reach the amusement park, output -1 instead."}},{"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\u003e0 0 0 10\r\n1\r\n0 5 5 8\r\n0 0 0 10\r\n2\r\n0 5 5 8\r\n-2 1 0 5\r\n0 0 0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn the first case, Biaoge can walk along the side of building, and no turn needed.\u003cbr\u003eIn the second case, two buildings block the direct way and Biaoge need to make 2 turns at least.\u003cbr\u003e"}}]}