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;
template <class T, class D>
class segtree {
 private:
  T zero;
  function<T(T, T)> combine;
  D dzero;
  function<D(D, D)> dcombine;
  function<T(T, D, int, int)> lcombine;
  vector<T> a, st;
  vector<D> delta;
  vector<bool> is_lazy;
  inline int L(int p) { return 2 * p; }
  inline int R(int p) { return 2 * p + 1; }
  inline int m(int s, int e) { return (s + e) / 2; }
  void pull(int p, int s, int e) {
    st[p] = combine(get_val(L(p), s, m(s, e)), get_val(R(p), m(s, e) + 1, e));
  }
  void lazy(int p, D v) { delta[p] = dcombine(delta[p], v), is_lazy[p] = true; }
  void unlazy(int p, int s, int e) {
    if (is_lazy[p]) {
      if (s != e) lazy(L(p), delta[p]), lazy(R(p), delta[p]);
      delta[p] = dzero, is_lazy[p] = false;
      pull(p, s, e);
    }
  }
  T get_val(int p, int s, int e) {
    return is_lazy[p] ? lcombine(st[p], delta[p], s, e) : st[p];
  }
  T build(int p, int s, int e) {
    delta[p] = dzero, is_lazy[p] = false;
    if (s == e) {
      return st[p] = a[s];
    } else {
      return st[p] =
                 combine(build(L(p), s, m(s, e)), build(R(p), m(s, e) + 1, e));
    }
  }

 public:
  const int size;
  segtree(T zero, function<T(T, T)> combine, D dzero,
          function<D(D, D)> dcombine, function<T(T, D, int, int)> lcombine,
          vector<T>& a, int size)
      : zero(zero),
        combine(combine),
        dzero(dzero),
        dcombine(dcombine),
        lcombine(lcombine),
        a(a),
        size(size) {
    st.resize(4 * (size + 1));
    delta.resize(4 * (size + 1));
    is_lazy.resize(4 * (size + 1));
    build(1, 1, size);
  }
  T query(int l, int r, int p, int s, int e) {
    if (l <= s && e <= r) {
      return get_val(p, s, e);
    } else if (r < s || e < l) {
      return zero;
    } else {
      unlazy(p, s, e);
      return combine(query(l, r, L(p), s, m(s, e)),
                     query(l, r, R(p), m(s, e) + 1, e));
    }
  }
  T query(int l, int r) { return query(l, r, 1, 1, size); }
  void update(int l, int r, D v, int p, int s, int e) {
    if (l <= s && e <= r) {
      lazy(p, v);
    } else if (!(r < s || e < l)) {
      unlazy(p, s, e);
      update(l, r, v, L(p), s, m(s, e)), update(l, r, v, R(p), m(s, e) + 1, e);
      pull(p, s, e);
    }
  }
  void update(int l, int r, D v) { update(l, r, v, 1, 1, size); }
};
template <class T, class Tdelta>
ostream& operator<<(ostream& os, const segtree<T, Tdelta>& t) {
  os << "[";
  bool comma = false;
  for (int i = 1; i <= t.size; i++) {
    comma ? void(os << ", ") : void(comma = true);
    os << t.query(i, i);
  }
  os << "]";
  return os;
}
struct lazy_flag {
  double m, a;
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, q;
  cin >> n >> q;
  vector<double> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  segtree<double, lazy_flag> s(
      0, plus<double>(), {1, 0},
      [](lazy_flag d1, lazy_flag d2) -> lazy_flag {
        return {d1.m * d2.m, d1.a * d2.m + d2.a};
      },
      [](double st, lazy_flag delta, int s, int e) {
        return st * delta.m + delta.a * (e - s + 1);
      },
      a, n);
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int l1, l2, r1, r2;
      cin >> l1 >> l2 >> r1 >> r2;
      double sum_l = s.query(l1, l2);
      double sum_r = s.query(r1, r2);
      double denom = (double)(r2 - r1 + 1) * (l2 - l1 + 1);
      s.update(l1, l2, {double(l2 - l1) / (l2 - l1 + 1), sum_r / denom});
      s.update(r1, r2, {double(r2 - r1) / (r2 - r1 + 1), sum_l / denom});
    } else {
      int l, r;
      cin >> l >> r;
      cout << fixed << setprecision(5) << s.query(l, r) << '\n';
    }
  }
  return 0;
}