Vasya 和 Petya 厌倦了学习,所以他们决定玩一个游戏。在游戏开始之前,Vasya 查看由 n 个整数组成的数组 a。一旦他记住了游戏的所有元素,游戏就开始了。 Vasya 闭上眼睛,Petya 执行以下两种动作之一:
1) Petya 表示 4 个整数 l1、r1、l2、r2 — 两个不相交线段的边界。之后,他将 [l1, r1] 段中的一个随机元素与 [l2, r2] 段中的另一个随机元素交换。
2) Petya 向 Vasya 询问 [l, r] 段中 a 的元素之和。
Vasya 是一位数学家,所以他回答 Petya 段中元素之和的数学期望。
你的任务是编写一个程序来回答第二类问题,就像 Vasya 所做的那样。换句话说,您的程序应该为每个第二种类型的查询打印 [l, r] 段中 a 元素总和的数学期望。
输入
第一行包含两个整数 n、q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105) — 数组中的元素数量和需要处理的查询数量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 数组的元素。
接下来的 q 行包含 Petya 类型 1 或 2 的动作。
如果是类型 1 动作,则该行包含 5 个整数 1、l1、r1、l2、r2 (1 ≤ l1 ≤ r1 ≤ n、1 ≤ l2 ≤ r2 ≤ n)。
如果是类型 2 查询,则该行包含 3 个整数 2、l、r (1 ≤ l ≤ r ≤ n)。
保证至少有一个类型2查询并且段[l1, r1], [l2, r2]没有公共元素。
输出
对于每个类型 2 查询,打印一个实数 - 段中元素总和的数学期望。
如果绝对或相对误差不超过 10 - 4,则您的答案将被视为正确 - 正式而言,如果 $${ \operatorname* { m i n } } ( | x - y |, { \frac { | x - y | } { x } } ) \leq 1 0 ^ { - 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
输出 #1
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
输出 #2
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
输出 #3
23.0000000 14.0000000 28.0133333 21.5733333 55.0000000