{"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 This story happened on the background of Star Trek.\u003cbr\u003e\u003cbr\u003e Spock, the deputy captain of Starship Enterprise, fell into Klingon’s trick and was held as prisoner on their mother planet Qo’noS.\u003cbr\u003e\u003cbr\u003e The captain of Enterprise, James T. Kirk, had to fly to Qo’noS to rescue his deputy. Fortunately, he stole a map of the maze where Spock was put in exactly.\u003cbr\u003e\u003cbr\u003e The maze is a rectangle, which has n rows vertically and m columns horizontally, in another words, that it is divided into n*m locations. An ordered pair (Row No., Column No.) represents a location in the maze. Kirk moves from current location to next costs 1 second. And he is able to move to next location if and only if:\u003cbr\u003e\u003cbr\u003e Next location is adjacent to current Kirk’s location on up or down or left or right(4 directions)\u003cbr\u003e Open door is passable, but locked door is not.\u003cbr\u003e Kirk cannot pass a wall\u003cbr\u003e\u003cbr\u003e There are p types of doors which are locked by default. A key is only capable of opening the same type of doors. Kirk has to get the key before opening corresponding doors, which wastes little time.\u003cbr\u003e\u003cbr\u003e Initial location of Kirk was (1, 1) while Spock was on location of (n, m). Your task is to help Kirk find Spock as soon as possible.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The input contains many test cases.\u003cbr\u003e\u003cbr\u003e Each test case consists of several lines. Three integers are in the first line, which represent n, m and p respectively (1\u0026lt;\u003d n, m \u0026lt;\u003d50, 0\u0026lt;\u003d p \u0026lt;\u003d10). \u003cbr\u003eOnly one integer k is listed in the second line, means the sum number of gates and walls, (0\u0026lt;\u003d k \u0026lt;\u003d500).\u003cbr\u003e\u003cbr\u003e There are 5 integers in the following k lines, represents x\u003csub\u003ei1\u003c/sub\u003e, y\u003csub\u003ei1\u003c/sub\u003e, x\u003csub\u003ei2\u003c/sub\u003e, y\u003csub\u003ei2\u003c/sub\u003e, g\u003csub\u003ei\u003c/sub\u003e; when g\u003csub\u003ei\u003c/sub\u003e \u0026gt;\u003d1, represents there is a gate of type gi between location (x\u003csub\u003ei1\u003c/sub\u003e, y\u003csub\u003ei1\u003c/sub\u003e) and (x\u003csub\u003ei2\u003c/sub\u003e, y\u003csub\u003ei2\u003c/sub\u003e); when g\u003csub\u003ei\u003c/sub\u003e \u003d 0, represents there is a wall between location (x\u003csub\u003ei1\u003c/sub\u003e, y\u003csub\u003ei1\u003c/sub\u003e) and (x\u003csub\u003ei2\u003c/sub\u003e, y\u003csub\u003ei2\u003c/sub\u003e), ( | x\u003csub\u003ei1\u003c/sub\u003e - x\u003csub\u003ei2\u003c/sub\u003e | + | y\u003csub\u003ei1\u003c/sub\u003e - y\u003csub\u003ei2\u003c/sub\u003e |\u003d1, 0\u0026lt;\u003d g\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003dp )\u003cbr\u003e\u003cbr\u003e Following line is an integer S, represent the total number of keys in maze. (0\u0026lt;\u003d S \u0026lt;\u003d50).\u003cbr\u003e\u003cbr\u003e There are three integers in the following S lines, represents x\u003csub\u003ei1\u003c/sub\u003e, y\u003csub\u003ei1\u003c/sub\u003e and q\u003csub\u003ei\u003c/sub\u003e respectively. That means the key type of q\u003csub\u003ei\u003c/sub\u003e locates on location (x\u003csub\u003ei1\u003c/sub\u003e, y\u003csub\u003ei1\u003c/sub\u003e), (1\u0026lt;\u003d q\u003csub\u003ei\u003c/sub\u003e\u0026lt;\u003dp)."}},{"title":"Output","value":{"format":"HTML","content":" Output the possible minimal second that Kirk could reach Spock. \u003cbr\u003e\u003cbr\u003e If there is no possible plan, output -1. \u003cbr\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\u003e4 4 9\r\n9\r\n1 2 1 3 2\r\n1 2 2 2 0\r\n2 1 2 2 0\r\n2 1 3 1 0\r\n2 3 3 3 0\r\n2 4 3 4 1\r\n3 2 3 3 0\r\n3 3 4 3 0\r\n4 3 4 4 0\r\n2\r\n2 1 2\r\n4 2 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}