题目描述

城市里有 $m$ 栋大楼，编号为 $1$ 到 $m$。大楼之间修有 $m-1$ 组天桥，任意两栋楼都可以通过天桥（可能经过其他楼）相互连通。第 $k$ 组天桥连接大楼 $u_k$ 和 $v_k$，每次通过需要缴纳过桥费 $w_k$。

第 $c$ 栋大楼只有第 $l_c$ 层到第 $r_c$ 层是开放的（$l_c \le r_c$）。用 $(c,p)$ 表示“第 $c$ 栋楼的第 $p$ 层”。只有当 $l_c \le p \le r_c$ 时，才能站在这个位置。

移动方式有两种：

• 坐电梯： 在同一栋楼 $c$ 内，可以从开放的第 $p_1$ 层到达开放的第 $p_2$ 层，要求 $p_2 \ge p_1$（电梯只能上行），不花钱。
• 过天桥： 若大楼 $c_1$ 和 $c_2$ 之间有天桥，且第 $p$ 层在两栋楼中都开放，即 $\max(l_{c_1},l_{c_2}) \le p \le \min(r_{c_1},r_{c_2})$，就可以从 $(c_1,p)$ 走到 $(c_2,p)$。楼层不变，需缴纳这组天桥的过桥费 $w$。

共有 $q$ 次询问，各次询问互不影响。每次询问给出九个整数 $c_s,p_s,c_t,p_t,c_a,p_a,c_b,p_b,x$：

• 小明要从 $S=(c_s,p_s)$ 出发，前往 $T=(c_t,p_t)$。
• 本次询问中会临时开通一条双向直达通道，连接 $A=(c_a,p_a)$ 和 $B=(c_b,p_b)$。从 $A$ 到 $B$ 或从 $B$ 到 $A$ 的费用都是 $x$，不受楼层限制。这条通道只在本次询问中有效。
• 保证 $S,T,A,B$ 所在的楼层都是开放的。

对每次询问，求小明从 $S$ 到 $T$ 的最少花费。如果无法到达，输出 No。

输入格式

从文件 cross.in 中读入数据。

第一行一个整数 $m$，表示大楼数量。

接下来 $m-1$ 行，每行三个整数 $u_k,v_k,w_k$，描述一组天桥。

接下来 $m$ 行，第 $c$ 行两个整数 $l_c,r_c$，表示第 $c$ 栋楼的开放楼层范围。

接下来一行一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行九个整数 $c_s,p_s,c_t,p_t,c_a,p_a,c_b,p_b,x$，描述一次询问。

输出格式

输出到文件 cross.out 中。

对每次询问输出一行。若能到达，输出最少花费（一个整数），否则输出 No。

样例1输入

4
1 2 3
1 3 5
3 4 2
10 40
20 60
15 45
30 70
3
2 25 4 65 1 10 4 70 1000
4 65 2 25 4 70 1 10 1000
2 45 4 65 2 30 3 40 7

样例1输出

10
1003
No

样例1解释

第 $1$ 次询问：在第 $25$ 层依次走 $2 \to 1 \to 3$，在 $3$ 号楼坐电梯升到第 $30$ 层，过天桥到 $4$ 号楼，再坐电梯升到第 $65$ 层。花费 $3+5+2=10$。

第 $2$ 次询问：起点在第 $65$ 层，而 $4$ 号楼通往 $3$ 号楼的天桥最高只到第 $45$ 层，电梯又不能下行，所以无法直接走天桥。可以先坐电梯升到第 $70$ 层，走直达通道到 $(1,10)$，再坐电梯升到第 $25$ 层，过天桥到达 $(2,25)$。花费 $1000+3=1003$。

第 $3$ 次询问：起点在第 $45$ 层，而 $2$ 号楼通往 $1$ 号楼的天桥最高只到第 $40$ 层，无法离开 $2$ 号楼；直达通道的两端也都无法到达，所以输出 No。

样例2输入

5
1 2 3
1 3 5
3 4 2
4 5 1
10 40
20 60
15 45
30 70
80 90
1
2 25 5 85 2 30 3 40 5

样例2输出

No

样例3

见选手下发文件夹中的 cross3.in 与 cross3.ans。

样例4

见选手下发文件夹中的 cross4.in 与 cross4.ans。

数据范围

对于所有测试数据，保证：

• $1 \le m \le 2 \times 10^5$，$1 \le q \le 5 \times 10^5$。
• $1 \le u_k,v_k \le m$，$1 \le w_k \le 10^9$。
• $0 \le l_c \le r_c \le 10^9$。
• $l_{c_s} \le p_s \le r_{c_s}$，$l_{c_t} \le p_t \le r_{c_t}$。
• $l_{c_a} \le p_a \le r_{c_a}$，$l_{c_b} \le p_b \le r_{c_b}$。
• $1 \le c_s,c_t,c_a,c_b \le m$，$0 \le x \le 10^9$。
• 天桥把所有大楼连成一棵树。

本题共 $24$ 个测试点，采用捆绑测试。只有通过一个子任务内的全部测试点，才能获得该子任务的全部分数；否则该子任务得 $0$ 分。

子任务编号	测试点编号	分值	$m \le$	$q \le$	特殊性质
1	$1 \sim 2$	5	10		无
2	$3 \sim 4$	8	200
3	$5 \sim 6$	10	3000
4	$7 \sim 8$	7	$2 \times 10^5$	$2 \times 10^5$	A
5	$9 \sim 11$	9			B
6	$12 \sim 13$	7			C
7	$14 \sim 15$	9			D
8	$16 \sim 17$	7			E
9	$18 \sim 21$	18			无
10	$22 \sim 24$	20		$5 \times 10^5$

特殊性质 A：所有大楼的开放楼层范围相同。

特殊性质 B：大楼排成一排，即第 $k$ 组天桥满足 $u_k=k,v_k=k+1$。

特殊性质 C：所有天桥都连向 $1$ 号楼，即第 $k$ 组天桥满足 $u_k=1,v_k=k+1$。

特殊性质 D：每次询问中，$c_s$ 与 $c_t$ 之间的树上简单路径经过的天桥数不超过 $50$。

特殊性质 E：每次询问的 $x=0$。