{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"农夫约翰的乡村邻里有N个农场(2 \u003c\u003d N \u003c\u003d 40,000),通常编号为1..N。一系列M(1 \u003c\u003d M \u003c\u003d 40,000)条垂直和水平道路连接这些农场,每条道路的长度不等(1 \u003c\u003d length \u003c\u003d 1000)。这些农场的地图可能看起来像下面的插图,其中为了清晰起见,农场被标记为F1..F7,连接农场之间的长度显示为(n):\u003cbr\u003e\u003cpre\u003e F1 --- (13) ---- F6 --- (9) ----- F3\r\u003cbr\u003e | |\r\u003cbr\u003e (3) |\r\u003cbr\u003e | (7)\r\u003cbr\u003e F4 --- (20) -------- F2 |\r\u003cbr\u003e | |\r\u003cbr\u003e (2) F5\r\u003cbr\u003e | \r\u003cbr\u003e F7 \u003c/pre\u003e作为ASCII图,当然不是精确的比例。\u003cbr\u003e\u003cbr\u003e每个农场最多可以通过道路直接连接至多四个其他农场,道路正好通向北、南、东和/或西。此外,农场仅位于道路的端点,并且每条道路的每个端点都可以找到一些农场。没有两条道路会交叉,并且恰好有一条路径(道路序列)连接每对农场。\u003cbr\u003e\u003cbr\u003e约翰失去了农场地图的纸质副本,他想从计算机的备份信息中重建它。这些数据包含了以下类似的行,每行对应一条道路:\u003cbr\u003e\u003cbr\u003e 从农场#23到农场#17有一条长度为10的向北的道路\u003cbr\u003e 从农场#1到农场#17有一条长度为7的向东的道路\u003cbr\u003e ...\u003cbr\u003e\u003cbr\u003e当约翰检索这些数据时,他偶尔会被来自他在导航上有挑战的邻居农夫鲍勃的问题打断:\u003cbr\u003e\u003cbr\u003e 农场#1和#23之间的曼哈顿距离是多少?\u003cbr\u003e\u003cbr\u003e约翰会尽可能地回答鲍勃的问题(有时他还没有足够的数据)。在上面的例子中,答案将是17,因为鲍勃想知道这对农场之间的“曼哈顿”距离。\u003cbr\u003e两点(x1,y1)和(x2,y2)之间的曼哈顿距离就是|x1-x2| + |y1-y2|(这是大城市出租车必须在完美的网格城市街道上行驶的距离,以连接两个x,y点)。\u003cbr\u003e\u003cbr\u003e当鲍勃询问特定一对农场时,约翰可能还没有足够的信息来推断它们之间的距离;在这种情况下,约翰会表示深深的歉意,并回答“-1”。\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cpre\u003e* Line 1: Two space-separated integers: N and M\r\u003cbr\u003e\r\u003cbr\u003e* Lines 2..M+1: Each line contains four space-separated entities, F1,\r\u003cbr\u003e F2, L, and D that describe a road. F1 and F2 are numbers of\r\u003cbr\u003e two farms connected by a road, L is its length, and D is a\r\u003cbr\u003e character that is either \u0027N\u0027, \u0027E\u0027, \u0027S\u0027, or \u0027W\u0027 giving the\r\u003cbr\u003e direction of the road from F1 to F2.\r\u003cbr\u003e\r\u003cbr\u003e* Line M+2: A single integer, K (1 \u0026lt;\u003d K \u0026lt;\u003d 10,000), the number of FB\u0027s\r\u003cbr\u003e queries\r\u003cbr\u003e\r\u003cbr\u003e* Lines M+3..M+K+2: Each line corresponds to a query from Farmer Bob\r\u003cbr\u003e and contains three space-separated integers: F1, F2, and I. F1\r\u003cbr\u003e and F2 are numbers of the two farms in the query and I is the\r\u003cbr\u003e index (1 \u0026lt;\u003d I \u0026lt;\u003d M) in the data after which Bob asks the\r\u003cbr\u003e query. Data index 1 is on line 2 of the input data, and so on.\u003c/pre\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cpre\u003e* Lines 1..K: One integer per line, the response to each of Bob\u0027s\r\u003cbr\u003e queries. Each line should contain either a distance\r\u003cbr\u003e measurement or -1, if it is impossible to determine the\r\u003cbr\u003e appropriate distance.\u003c/pre\u003e"}},{"title":"样例","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\u003e7 6\r\n1 6 13 E\r\n6 3 9 E\r\n3 5 7 S\r\n4 1 3 N\r\n2 4 20 W\r\n4 7 2 S\r\n3\r\n1 6 1\r\n1 4 3\r\n2 6 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\r\n-1\r\n10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"在时间1,约翰知道1和6之间的距离是13。\u003cbr\u003e在时间3,1和4之间的距离仍然未知。\u003cbr\u003e最后,位置6比2向西3个单位,向北7个单位,所以距离是10。\u003cbr\u003e"}}]}