В Древесном мире наступает Новый год! В этом мире, как понятно из названия, есть 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. Санты хотели бы знать математическое ожидание цены, необходимой для построения сети.
Однако, как мы сказали, каждый год длина ровно одной дороги уменьшается. Таким образом, Санты хотят просчитать математическое ожидание после каждого изменения длины. Помогите им посчитать требуемые значения.
Выходные данные
Выведите q чисел. После каждого из изменений выведите строку с математическим ожиданием цены, необходимой для постройки сети сообщения в Древесном мире. Ответ будет считаться корректным, если его абсолютная или относительная погрешность не превышают 10 - 6.
Примечание
Рассмотрим первый пример. Есть 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).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|