{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Nemo is a naughty boy. One day he went into the deep sea all by himself. Unfortunately, he became lost and couldn\u0027t find his way home. Therefore, he sent a signal to his father, Marlin, to ask for help.\r\u003cbr\u003eAfter checking the map, Marlin found that the sea is like a labyrinth with walls and doors. All the walls are parallel to the X-axis or to the Y-axis. The thickness of the walls are assumed to be zero.\r\u003cbr\u003eAll the doors are opened on the walls and have a length of 1. Marlin cannot go through a wall unless there is a door on the wall. Because going through a door is dangerous (there may be some virulent medusas near the doors), Marlin wants to go through as few doors as he could to find Nemo.\r\u003cbr\u003eFigure-1 shows an example of the labyrinth and the path Marlin went through to find Nemo.\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/6f22e4b0e6545e9f66d0871df89b552f?v\u003d1714050769\"\u003e\u003c/center\u003e\r\u003cbr\u003eWe assume Marlin\u0027s initial position is at (0, 0). Given the position of Nemo and the configuration of walls and doors, please write a program to calculate the minimum number of doors Marlin has to go through in order to reach Nemo."}},{"title":"Input","value":{"format":"HTML","content":"The input consists of several test cases. Each test case is started by two non-negative integers M and N. M represents the number of walls in the labyrinth and N represents the number of doors. \r\u003cbr\u003eThen follow M lines, each containing four integers that describe a wall in the following format: \r\u003cbr\u003ex y d t \r\u003cbr\u003e(x, y) indicates the lower-left point of the wall, d is the direction of the wall -- 0 means it\u0027s parallel to the X-axis and 1 means that it\u0027s parallel to the Y-axis, and t gives the length of the wall. \r\u003cbr\u003eThe coordinates of two ends of any wall will be in the range of [1,199]. \r\u003cbr\u003eThen there are N lines that give the description of the doors: \r\u003cbr\u003ex y d \r\u003cbr\u003ex, y, d have the same meaning as the walls. As the doors have fixed length of 1, t is omitted. \r\u003cbr\u003eThe last line of each case contains two positive float numbers: \r\u003cbr\u003ef1 f2 \r\u003cbr\u003e(f1, f2) gives the position of Nemo. And it will not lie within any wall or door. \r\u003cbr\u003eA test case of M \u003d -1 and N \u003d -1 indicates the end of input, and should not be processed."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, in a separate line, please output the minimum number of doors Marlin has to go through in order to rescue his son. If he can\u0027t reach Nemo, output -1."}},{"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\u003e8 9\r\n1 1 1 3\r\n2 1 1 3\r\n3 1 1 3\r\n4 1 1 3\r\n1 1 0 3\r\n1 2 0 3\r\n1 3 0 3\r\n1 4 0 3\r\n2 1 1\r\n2 2 1\r\n2 3 1\r\n3 1 1\r\n3 2 1\r\n3 3 1\r\n1 2 0\r\n3 3 0\r\n4 3 1\r\n1.5 1.5\r\n4 0\r\n1 1 0 1\r\n1 1 1 1\r\n2 1 1 1\r\n1 2 0 1\r\n1.5 1.7\r\n-1 -1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}