29373번 - Штурвал 다국어

문제

Чёрная жемчужина --- старый и потрёпанный бесчисленными плаваниями корабль. Не остался нетронутым и штурвал --- главный орган управления кораблём. Если штурвала не будет, то управлять кораблём будет невозможно и он сгинет в пучине. % отчаяния

Штурвал состоит из 2ドルn$ деревянных палок, соединённых между собой в $n+1$-ом местах следующим образом (на рисунке $n=8$):

Во время боя некоторые соединительные палки могут быть сломаны. Штурвал считается целым, если ни одно соединение не отпало от центра. Например, левый штурвал целый, а правый --- нет.

Для защиты корабля от нападения коварных кальмаров, было решено покрасить некоторые его части специальной кальмарозащитной краской. Та же участь постигла и штурвал. Краски мало, и поэтому ее нужно экономить.

Про каждую соединительную палку известно, сколько краски необходимо на то, чтобы ее покрасить. Решено покрасить штурвал так, чтобы при нападении кальмаров он не оказался сломанным (то есть, любой узел был бы связан с центром только по покрашенным палкам), и чтобы на это ушло минимальное число краски.

Периодически производится ремонт штурвала, который заключается в замене одной из соединительных палок на новую, у которой количество краски, необходимое на ее обработку, может отличаться от этого же количества у старой палки. Вам было поручено выяснить, какое наименьшее количество краски можно потратить на обработку штурвала до всех его ремонтов, после первого, после второго, \ldots, после $q$-го.

입력

В первой строке задано количество рукояток штурвала $n$ (3ドル \le n \le 100{,円}000$). Во второй строке заданы 2ドルn$ чисел --- необходимое количество краски для покраски ребра 0ドル$--1ドル,ドル 0ドル$--2ドル,ドル $\ldots,ドル 0ドル$--$(n-1),ドル 0ドル$--$n,ドル 1ドル$--2ドル,ドル 2ドル$--3ドル,ドル $\ldots,ドル $(n-1)$--$n,ドル $n$--1ドル$.

В третьей строке задано число $q$ (0ドル \le n \le 100{,円}000$) --- количество ремонтов штурвала. В следующих $q$ строках в формате $a_i, b_i, w_i$ ($-10^9 \le w_i \le 10^9$), где $a_i$ и $b_i$ --- номера соединений, связанных заменяемой палкой, а $w_i$ --- количество краски, необходимое на обработку новой палки, заданы сами запросы. Гарантируется, что $a_i$ и $b_i$ корректны.

출력

Выведите $q+1$ число: начальное необходимое количество краски, количество краски, необходимое для покраски после первого ремонта, после второго ремонта, $\ldots,ドル после $n$-го ремонта.

제한

힌트