У Санты есть бесконечное число конфет каждого из \(m\) вкусов. Вам дано корневое дерево с \(n\) вершинами. Корень дерева — вершина с номером \(1\). Каждая вершина содержит ровно одну конфету, \(i\)-я вершина содержит конфету вкуса \(f_i\).
Иногда Санта боится, что конфеты вкуса \(k\) испортились. Он выбирает любую вершину \(x\) случайным образом и посылает поддерево вершины \(x\) кондитерам на замену. Во время замены все конфеты вкуса \(k\) в поддереве заменяются на новые конфеты того же вкуса, а конфеты не вкуса \(k\) остаются неизменными. После замены дерево возвращается в состояние, в котором оно было до замены.
Настоящая цена замены одной конфеты вкуса \(k\) равна \(c_k\) (дана для каждого \(k\)). Однако, для простоты вычислений кондитеры берут за каждое посланное им поддерево одинаковую сумму \(C\) вне зависимости от того, какое поддерево выбрано, сколько конфет в поддереве и какого вкуса они.
Предположим, что для заданного вкуса \(k\) вероятность выбора каждой вершины Сантой для посылки на замену одинакова для всех вершин. Вам нужно найти математическое ожидание ошибки в подсчёте стоимости замены конфет вкуса \(k\). Ошибка в подсчёте стоимости вычисляется так:
\(\) Ошибка\ E(k) =\ (настоящая\ стоимость\ замены\ –\ цена,\ взятая\ кондитерами) ^ 2.\(\)
Обратите внимание, что настоящая стоимость замены равна стоимости замены одной конфеты вкуса \(k\), умноженной на количество конфет этого вкуса в поддереве.
Иногда Санта заменяет конфету в вершине \(x\) на конфету некоторого вкуса из его кармана.
Ваша программа должна уметь обрабатывать два типа запросов:
- Изменить вкус конфеты в вершине \(x\) на вкус \(w\).
- Подсчитайте математическое ожидание ошибки подсчёта стоимости замены конфет для заданного вкуса \(k\).
Входные данные
Первая строка входных данных содержит четыре целых числа \(n\) (\(2 \leqslant n \leqslant 5 \cdot 10^4\)), \(m\), \(q\), \(C\) (\(1 \leqslant m, q \leqslant 5 \cdot 10^4\), \(0 \leqslant C \leqslant 10^6\)) — число вершин в графе, количество различных вкусов конфет, число запросов и цена, которую кондитеры берут за замену поддерева? соответственно.
Вторая строка содержит \(n\) целых чисел \(f_1, f_2, \dots, f_n\) (\(1 \leqslant f_i \leqslant m\)), где \(f_i\) — изначальный вкус конфеты в \(i\)-й вершине.
В третьей строке содержится \(n - 1\) целое число \(p_2, p_3, \dots, p_n\) (\(1 \leqslant p_i \leqslant n\)), где \(p_i\) — родитель \(i\)-й вершины.
Следующая строка содержит \(m\) целых чисел \(c_1, c_2, \dots c_m\) (\(1 \leqslant c_i \leqslant 10^2\)), где \(c_i\) — стоимость замены одной конфеты со вкусом \(i\).
Следующие \(q\) строк описывают запросы. Каждая строка начинается с целого числа \(t\) (\(1 \leqslant t \leqslant 2\)) — типа запроса.
Если \(t = 1\), тогда эта строка описывает запрос первого типа. За ним следует два целых числа \(x\) и \(w\) (\(1 \leqslant x \leqslant n\), \(1 \leqslant w \leqslant m\)) — Санта заменяет конфету в вершине \(x\) на конфету вкуса \(w\).
Иначе, если \(t = 2\), строка описывает запрос второго типа и после него следует целое число \(k\) (\(1 \leqslant k \leqslant m\)) — выведите математическое ожидание ошибки в подсчёте стоимости замены конфет для данного вкуса \(k\).
Вершины пронумерован с \(1\) до \(n\). Вершина \(1\) является корнем.
Выходные данные
Выведите ответ на каждый запрос второго типа в отдельной строке.
Ваш ответ будет принят, если его относительная или абсолютная погрешность не превышает \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет засчитан, если и только если \(\frac{|a-b|}{max(1,b)}\leqslant 10^{-6}\).
Примечание
Для \(1\)-го запроса ошибка в подсчёте стоимости замены для вкуса \(1\) равна \(66^2\), \(66^2\) и \((-7)^2\), если выбран \(1\), \(2\) и \(3\) соответственно. Так как вероятность выбора каждой из вершин одинакова, математическое ожидание ошибки равно \(\frac{66^2+66^2+(-7)^2}{3}\).
Аналогично, для \(2\)-го запроса ожидаемое значение ошибки равно \(\frac{41^2+(-7)^2+(-7)^2}{3}\).
После \(3\)-го запроса, вкус конфеты на вершине \(2\) изменится с \(1\) на \(3\).
Для \(4\)-го запроса ожидаемое значение ошибки равно \(\frac{(-7)^2+(-7)^2+(-7)^2}{3}\).
Аналогично для \(5\)-го запроса ожидаемое значение ошибки равно \(\frac{89^2+41^2+(-7)^2}{3}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5 5 7
3 1 4
1 1
73 1 48 85 89
2 1
2 3
1 2 3
2 1
2 3
|
2920.333333333333
593.000000000000
49.000000000000
3217.000000000000
|