$N$ вершин образуют дерево. Вершины пронумерованы от $0$ до $N-1$. Рёбра имеют неотрицательные целые веса.

Необходимо выполнять следующие запросы:

• 1 u v w x: удалить ребро между $u$ и $v$ и добавить ребро между $v$ и $w$ с весом $x$. Гарантируется, что ребро между $u$ и $v$ существует. Гарантируется, что после выполнения операции граф остаётся деревом. ($0 \le x \le 100\,000$)
• 2 k x_1 x_2 ... x_k: для вершин $x_1, x_2, \ldots, x_k$ рассмотрим все уникальные простые пути между каждой парой $x_i$ и $x_j$ для всех $1 \le i < j \le k$. Требуется вывести сумму весов всех рёбер, входящих в объединение этих путей. Все $x_i$ различны. ($1 \le k \le n$)

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

Первая строка содержит размер дерева $N$. ($2 \le N \le 100{,}000$)

Следующие $N-1$ строк содержат три целых числа $u, v, w$, означающих ребро с весом $w$, соединяющее вершины $u$ и $v$. ($0 \le u, v \le N - 1$, $0 \le w \le 100{,}000$)

Следующая строка содержит количество запросов $Q$. ($1 \le Q \le 100{,}000$)

Следующие $Q$ строк содержат запросы, описанные выше.

Сумма $k$ по всем запросам типа $2$ находится в диапазоне от $1$ до $100{,}000$ включительно.

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

Для каждого запроса типа $2$ выведите результат в отдельной строке в порядке поступления запросов.

Примеры

Ввод 1

7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
4
1 1 4 5 7
2 3 0 4 6
1 0 2 1 8
2 3 0 4 6

Вывод 1

20
27