D. Новогоднее взаимодействие Санта-Клаусов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В Древесном мире наступает Новый год! В этом мире, как понятно из названия, есть n городов, соединенных n - 1 дорогой, и между каждыми двумя различными городами всегда существует путь. Города пронумерованы целыми числами от 1 до n. Дороги пронумерованы целыми числами от 1 до n - 1. Определим d(u, v) как суммарную длину дорог на пути между городом u и городом v.

Отдавая дань традиции, народ в Древесном мире ремонтирует ровно по дороге в год. В результате длина этой дороги уменьшается. Известно, что в i-м году длина ri-й дороги станет wi, что короче прежней длины этой же дороги. Предположим, что текущий год — это год 1.

Три Санта-Клауса планируют раздавать подарки всем детям Древесного мира ежегодно. Для этого им надо подготовиться, в целях чего они выберут три различных города c1, c2, c3, и создадут в каждом из этих городов по одному складу: k-й (1 ≤ k ≤ 3) Санта-Клаус будет отвечать за склад в городе ck.

Трем Санта-Клаусам очень скучно сидеть на складах поодиночке. Поэтому они решили построить сеть сообщения, предназначенную только для Сант! Затраты, необходимые для того, чтобы построить подобную сеть, равны d(c1, c2) + d(c2, c3) + d(c3, c1) долларам. Санты слишком заняты, чтобы искать лучшее место, так что они решили выбрать c1, c2, c3 случайно равновероятно среди всех троек различных чисел от 1 до n. Санты хотели бы знать математическое ожидание цены, необходимой для построения сети.

Однако, как мы сказали, каждый год длина ровно одной дороги уменьшается. Таким образом, Санты хотят просчитать математическое ожидание после каждого изменения длины. Помогите им посчитать требуемые значения.

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

В первой строке записано целое число n (3 ≤ n ≤ 105) — количество городов в Древесном мире.

В следующих n - 1 строках описаны дороги. В i-ой из этих строк (1 ≤ i ≤ n - 1) записаны три целых числа через пробел ai, bi, li (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ li ≤ 103), обозначающих, что i-я дорога соединяет города ai и bi, а длина i-й дороги равна li.

В следующей строке записано целое число q (1 ≤ q ≤ 105) — количество изменений длин дорог.

Следующие q строк описывают изменения длин. В j-й из них (1 ≤ j ≤ q) записано два целых числа через пробел — rj, wj (1 ≤ rj ≤ n - 1, 1 ≤ wj ≤ 103). Это означает, что после j-го ремонта длина rj-й дороги равняется wj. Гарантируется, что wj меньше длины rj-й дороги на тот год. Одну и ту же дорогу можно ремонтировать несколько раз.

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

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

Примеры
Входные данные
3
2 3 5
1 3 3
5
1 4
2 2
1 2
2 1
1 1
Выходные данные
14.0000000000
12.0000000000
8.0000000000
6.0000000000
4.0000000000
Входные данные
6
1 5 3
5 3 2
6 1 7
1 4 4
5 2 3
5
1 2
2 1
3 5
4 1
5 2
Выходные данные
19.6000000000
18.6000000000
16.6000000000
13.6000000000
12.6000000000
Примечание

Рассмотрим первый пример. Есть 6 троек: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Так как n = 3, затраты на построение сети всегда равны d(1, 2) + d(2, 3) + d(3, 1) для всех троек. Таким образом, матожидание стоимости равняется d(1, 2) + d(2, 3) + d(3, 1).