Вам дан неориентированный граф специального вида. Он состоит из $$$2n$$$ вершин, пронумерованных от $$$1$$$ до $$$2n$$$. Граф обладает следующими свойствами:
- в нем ровно $$$3n-2$$$ ребра: $$$n$$$ ребер соединяют вершины с четными номерами и вершины с нечетными номерами, $$$n - 1$$$ ребер соединяют вершины с нечетными номерами друг с другом, и $$$n - 1$$$ ребер соединяют вершины с четными номерами друг с другом;
- для каждого ребра $$$(u, v)$$$ между вершинами с нечетными номерами существует ребро $$$(u + 1, v + 1)$$$, и наоборот;
- для каждого нечетного числа $$$u \in [1, 2n - 1]$$$ существует ребро $$$(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$$$-й запрос.
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
3 15 4
Граф в первом тесте выглядит следующим образом:
