Вам дан простой неориентированный граф содержащий $n+1$ вершин пронумерованных $0, 1, \ldots, n$ и $n + m$ ребер.

Вес ребра между вершинами $0$ и $i$ равен $a_i$ для $1 \leq i \leq n$.

Вес ребра между вершинами $u_i$ и $v_i$ равен $w_i$ для $1 \leq i \leq m$.

Вам нужно ответить на $q$ запросов, каждый запрос содержит два целых числа $i, w$, вам нужно поменять вес ребра между вершинами $0$ и $i$ на $w$ и найти вес минимального остовного дерева в графе.

Обратите внимание, что запросы перманенты, т.е. изменения остаются навсегда.

Входные данные

В первой строке записаны два целых числа $n, m$ ($2 \leq n \leq 300\,000, 0 \leq m \leq 300\,000$).

Во второй строке записаны $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).

В каждой из следующих $m$ строк записаны три целых числа $u_i, v_i, w_i$ ($1 \leq u_i, v_i \leq n, 0 \leq w_i \leq 10^9$).

Гарантируется, что данный граф простой, а именно не содержит петель и кратных ребер.

В следующей строке записано одно целое число $q$ ($1 \leq q \leq 300\,000$).

В каждой из следующих $q$ строк записаны два целых числа $i, w$ ($1 \leq i \leq n, 1 \leq w \leq 10^9$).

Выходные данные

В каждой строке выведите одно целое число "– вес минимального остовного дерева в графе после $i$ запросов.

Подзадачи