Олимпиадный тренинг

Задача . G. Двойное дерево

Задача

Темы: Деревья кратчайшие пути разделяй и властвуй Структуры данных *2700

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

Примечание

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

$\text{[math]}$