| Codeforces Round 448 (Div. 2) |
|---|
| Закончено |
Петя и Вася устали от учебы и решили сыграть в игру. Перед началом игры Вася смотрит на массив a из n элементов и запоминает его. Далее он закрывает глаза, а Петя q раз делает одно из двух действий:
1) Называет 4 целых числа l1, r1, l2, r2 — границы двух непересекающихся отрезков. После этого Петя берет случайный элемент массива a из отрезка [l1, r1] и меняет местами его со случайным элементом из отрезка [l2, r2].
2) Спрашивает у Васи сумму элементов массива a на отрезке [l, r].
Вася — математик, поэтому на вопросы о сумме он отвечает математическим ожиданием суммы элементов на отрезке.
Ваша задача — написать программу, которая отвечает на запросы так, как это делал бы Вася. То есть для каждого запроса второго типа выводит математическое ожидание суммы элементов массива a из отрезка [l, r].
Первая строка содержит два целых числа n, q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105) — размер массива и количество действий Пети соответственно.
Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 109) — элементы массива.
Далее следуют q строк, содержащие действия Пети.
Если это действие 1-го типа, то строка содержит 5 целых чисел 1, l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n).
Если же это действие 2-го типа, то строка содержит 3 целых числа 2, l, r (1 ≤ l ≤ r ≤ n).
Гарантируется, что не существует элемента одновременно принадлежащего обоим отрезкам [l1, r1], [l2, r2] из действия первого типа, а также среди действий есть хотя бы одно 2-го типа.
Для каждого действия 2-го типа выведите одно вещественное число — математическое ожидание суммы элементов массива на отрезке.
Относительная или абсолютная ошибка не должна превышать 10 - 4. То есть ваш ответ будет засчитан, если 
, где x и y это ответ жюри и ваш соответственно.
4 4
1 1 2 2
1 2 2 3 3
2 1 2
1 1 2 3 4
2 1 2
3.0000000
3.0000000
10 5
1 1 1 1 1 2 2 2 2 2
1 1 5 6 10
2 1 5
1 1 5 6 10
1 1 5 6 10
2 6 10
6.0000000
8.0400000
10 10
1 2 3 4 5 6 7 8 9 10
1 1 5 6 10
1 1 5 6 10
2 1 5
1 1 3 6 9
2 1 3
1 5 7 8 10
1 1 1 10 10
2 1 5
2 7 10
2 1 10
23.0000000
14.0000000
28.0133333
21.5733333
55.0000000
