Петя и Вася устали от учебы и решили сыграть в игру. Перед началом игры Вася смотрит на массив a из n элементов и запоминает его. Далее он закрывает глаза, а Петя q раз делает одно из двух действий:
1) Называет 4 целых числа l1, r1, l2, r2 — границы двух непересекающихся отрезков. После этого Петя берет случайный элемент массива a из отрезка [l1, r1] и меняет местами его со случайным элементом из отрезка [l2, r2].
2) Спрашивает у Васи сумму элементов массива a на отрезке [l, r].
Вася — математик, поэтому на вопросы о сумме он отвечает математическим ожиданием суммы элементов на отрезке.
Ваша задача — написать программу, которая отвечает на запросы так, как это делал бы Вася. То есть для каждого запроса второго типа выводит математическое ожидание суммы элементов массива a из отрезка [l, r].
Выходные данные
Для каждого действия 2-го типа выведите одно вещественное число — математическое ожидание суммы элементов массива на отрезке.
Относительная или абсолютная ошибка не должна превышать 10 - 4. То есть ваш ответ будет засчитан, если 
, где x и y это ответ жюри и ваш соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|
|
3
|
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
|