G. Двойное дерево
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф специального вида. Он состоит из $$$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
Примечание

Граф в первом тесте выглядит следующим образом: