Problem: Vasya and Petya were tired of studying so they decided to play a game. Before the game begins Vasya looks at array a consisting of n integers. As soon as he remembers all elements of a the game begins. Vasya closes his eyes and Petya does q actions of one of two types:

1) Petya says 4 integers l1, r1, l2, r2 — boundaries of two non-intersecting segments. After that he swaps one random element from the [l1, r1] segment with another random element from the [l2, r2] segment.

2) Petya asks Vasya the sum of the elements of a in the [l, r] segment.

Vasya is a mathematician so he answers Petya the mathematical expectation of the sum of the elements in the segment.

Your task is to write a program which will answer the second type questions as Vasya would do it. In other words your program should print the mathematical expectation of the sum of the elements of a in the [l, r] segment for every second type query.

Input

The first line contains two integers n, q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105) — the number of elements in the array and the number of queries you need to handle.

The second line contains n integers ai (1 ≤ ai ≤ 109) — elements of the array.

The next q lines contain Petya's actions of type 1 or 2.

If it is a type 1 action then the line contains 5 integers 1, l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n).

If it is a type 2 query then the line contains 3 integers 2, l, r (1 ≤ l ≤ r ≤ n).

It is guaranteed that there is at least one type 2 query and segments [l1, r1], [l2, r2] don't have common elements. 

Output

For each type 2 query print one real number — the mathematical expectation of the sum of elements in the segment.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 4 — formally, the answer is correct if <image> where x is jury's answer and y is yours.

Examples

Input

4 4
1 1 2 2
1 2 2 3 3
2 1 2
1 1 2 3 4
2 1 2


Output

3.0000000
3.0000000


Input

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


Output

6.0000000
8.0400000


Input

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


Output

23.0000000
14.0000000
28.0133333
21.5733333
55.0000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
double a[100009];
struct node {
  int si, ei;
  double v, mlz, alz;
  node(int sii = 0, int eii = 0, double vv = 0, double ml = 1, double al = 0) {
    si = sii;
    ei = eii;
    v = vv;
    mlz = ml, alz = al;
  }
};
struct seg_tree {
  node nd[4 * 100009];
  void init(int in, int s, int e) {
    node &n = nd[in];
    if (s == e) {
      n = node(s, e, a[s]);
      return;
    }
    int mid = (s + e) / 2;
    init(2 * in, s, mid);
    init(2 * in + 1, mid + 1, e);
    n = merge(nd[2 * in], nd[2 * in + 1]);
  }
  void prop(int in) {
    node &n = nd[in];
    n.v = n.v * n.mlz + n.alz * (n.ei - n.si + 1);
    if (n.si != n.ei) {
      nd[2 * in].mlz *= n.mlz;
      nd[2 * in + 1].mlz *= n.mlz;
      nd[2 * in].alz = n.mlz * nd[2 * in].alz + n.alz;
      nd[2 * in + 1].alz = n.mlz * nd[2 * in + 1].alz + n.alz;
    }
    n.mlz = 1, n.alz = 0;
  }
  node merge(node a, node b) { return node(a.si, b.ei, a.v + b.v); }
  void upd_lz(node &n, pair<double, double> lz) {
    n.mlz *= lz.first;
    n.alz = lz.first * n.alz + lz.second;
  }
  node query_r(int in, int s, int e) {
    prop(in);
    node &n = nd[in];
    if (n.si == s && n.ei == e) return n;
    int mid = (n.si + n.ei) / 2;
    if (e <= mid)
      return query_r(2 * in, s, e);
    else if (s > mid)
      return query_r(2 * in + 1, s, e);
    else
      return merge(query_r(2 * in, s, mid), query_r(2 * in + 1, mid + 1, e));
  }
  void update_r(int in, int s, int e, pair<double, double> v) {
    node &n = nd[in];
    if (n.si == s && n.ei == e) {
      upd_lz(n, v);
      return;
    }
    prop(in);
    int mid = (n.si + n.ei) / 2;
    if (e <= mid)
      update_r(2 * in, s, e, v);
    else if (s > mid)
      update_r(2 * in + 1, s, e, v);
    else {
      update_r(2 * in, s, mid, v);
      update_r(2 * in + 1, mid + 1, e, v);
    }
    prop(2 * in);
    prop(2 * in + 1);
    n = merge(nd[2 * in], nd[2 * in + 1]);
  }
};
seg_tree st;
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    a[i] = x;
  }
  st.init(1, 1, n);
  while (q--) {
    int ty;
    scanf("%d", &ty);
    if (ty == 1) {
      int l1, r1, l2, r2;
      scanf("%d %d", &l1, &r1);
      scanf("%d %d", &l2, &r2);
      double p = r1 - l1 + 1, q = r2 - l2 + 1;
      double sp, sq;
      sp = st.query_r(1, l1, r1).v;
      sq = st.query_r(1, l2, r2).v;
      st.update_r(1, l1, r1, make_pair((p - 1) / p, sq / (p * q)));
      st.update_r(1, l2, r2, make_pair((q - 1) / q, sp / (p * q)));
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      double ans = st.query_r(1, l, r).v;
      printf("%.10f\n", ans);
    }
  }
}