E. Археология
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

На этот раз вам нужно помочь группе ученых-исследователей на одном острове в Тихом Океане. Они изучают культуру древних племен, живших на этом острове много лет назад.

Всего было раскопано n деревень. Некоторые пары деревень были соединены дорогами. По дорогам можно было двигаться в обоих направлениях. Всего было ровно n - 1 дорог, и из любой деревни можно было добраться в любую другую.

Племена были неспокойны и часто воевали. В результате войн некоторые деревни полностью уничтожались. В более спокойные годы некоторые из деревень возрождались заново.

В каждый момент времени использовались только те дороги, которые принадлежали какому-либо кратчайшему пути между двумя существующими в данный момент деревнями. Другими словами, использовалось наименьшее подмножество дорог так, чтобы из любой существующей деревни можно было добраться до любой другой существующей. Обратите внимание, что за всю историю острова существовало ровно n - 1 дорог, найденных исследователями, а других дорог никогда не было.

Исследователи полагают, что наблюдения за суммарной длиной используемых дорог в разные моменты времени помогут им лучше понять культуру племен и ответить на ряд исторических вопросов.

Вам будет предоставлена вся история существования племен. Ваша задача — определить суммарную длину используемых дорог в некоторые из моментов времени.

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

В первой строке дано целое число n (1 ≤ n ≤ 105) — количество деревень. В последующих n - 1 строках описаны дороги. i-ая из этих строк содержит три целых числа ai, bi и ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 109, 1 ≤ i < n) — номера деревень, которые соединяет i-ая дорога и ее длина. Числа в строках записаны через пробел.

В следующей строке дано целое число q (1 ≤ q ≤ 105) — количество запросов. Далее идут q запросов по одному в строке, упорядоченные по времени. Каждый запрос имеет один из трех типов:

  • «+ x» — деревня с номером x возрождается (1 ≤ x ≤ n).
  • «- x» — деревня с номером x уничтожается (1 ≤ x ≤ n).
  • «?» — в этот момент времени археологи хотят знать суммарную длину используемых дорог.

Гарантируется, что запросы не противоречат друг другу, то есть не будет запросов на уничтожение несуществующих деревень или возрождение уже существующих. Гарантируется, что имеется хотя бы один запрос типа «?». Также гарантируется, что по заданным дорогам из любой деревни можно добраться в любую другую.

Считается, что в начальный момент времени ни одной деревни не существует.

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

На каждый запрос типа «?» выведите суммарную длину используемых дорог в отдельной строке. Ответы за запросы должны быть выведены в том порядке, в котором запросы перечислены во входных данных.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
6
1 2 1
1 3 5
4 1 7
4 5 3
6 4 2
10
+ 3
+ 1
?
+ 6
?
+ 5
?
- 6
- 3
?
Выходные данные
5
14
17
10