给你一个特殊的无向图。它由 $$$2n$$$ 个顶点组成,编号从 $$$1$$$ 到 $$$2n$$$。该图具有以下属性:
- 图中正好有 $$$3n-2$$$ 边:$$$n$$$ 边将奇数编号的顶点与偶数编号的顶点连接起来,$$$n - 1$$$ 边将奇数编号的顶点彼此连接,$$$n - 1$$$ 边将偶数编号的顶点彼此连接;
- 对于一对奇数顶点之间的每条边 $$$(u, v)$$$,都存在一条边 $$$(u + 1, v + 1)$$$,反之亦然;
- 对于 [1, 2n - 1]$$$ 中的每个奇数 $$$u \,存在一条边 $$$(u, u + 1)$$$;
- 图已连接;此外,如果我们删除其中所有偶数的顶点,以及所有与它们相关的边,该图将成为一棵树(同样适用于删除奇数顶点)。
因此,图可以表示为具有相同结构的两棵树,以及将第一棵树的每个顶点连接到第二棵树的相应顶点的$$$n$$$条边。
图形的边缘被加权。图中某些简单路径的长度是遍历边的权重之和。
您将收到对此图表的 $$$q$$$ 查询;在每个查询中,系统都会要求您计算该图中某对顶点之间的最短路径的长度。您能回答所有问题吗?
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$w_{1, 2}$$$, $$$w_{3,4}$$$, ..., $$$w_{2n - 1, 2n}$$$ ($$$1 \le w_{i, i + 1} \le 10^{12}$$$)。这些整数描述了连接奇数顶点和偶数顶点的边的权重。
然后是 $$$n-1$$$ 行。第 $$$i$$$ 行包含四个整数 $$$x_i$$$、$$$y_i$$$、$$$w_{i, 1}$$$ 和 $$$w_{i, 2}$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$, $$$1 \le w_{i, j} \le 10^{12}$$$);它描述了两条边:一条连接 $$$2x_i - 1$$$ 与 $$$2y_i - 1$$$ 并具有权重 $$$w_{i, 1}$$$;另一个连接 $$$2x_i$$$ 与 $$$2y_i$$$ 并具有权重 $$$w_{i, 2}$$$。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 6 \cdot 10^5$$$) — 查询数。
接下来是 $$$q$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le 2n$$$, $$$u_i \ne v_i$$$),描述一个查询“计算顶点之间的最短路径的长度” $$$u_i$$$ 和 $$$v_i$$$"。
输出
打印 $$$q$$$ 整数,第 $$$i$$$ 个整数应等于第 $$$i$$$ 个查询的答案。
示例
输入 #1
5 3 6 15 4 8 1 2 5 4 2 3 5 7 1 4 1 5 1 5 2 1 3 1 2 5 6 1 10
输出 #1
3 15 4
注意
第一个测试中的图表如下所示: