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;
using ld = long double;
#pragma warning(disable : 4996)
const pair<int, ld> Zero1(make_pair(0, 0));
const pair<ld, ld> Zero2(make_pair(1, 0));
struct Node {
  pair<int, ld> sum;
  pair<ld, ld> lazy;
  Node() : sum(Zero1) { lazy = Zero2; }
};
struct lazy_segtree {
  int N;
  vector<Node> dat;
  lazy_segtree(int n) : N(1) {
    while (N < n) N *= 2;
    dat.resize(2 * N);
  }
  pair<ld, ld> lazy_connect(const pair<ld, ld> l, const pair<ld, ld> r) {
    return make_pair(l.first * r.first, l.second * r.first + r.second);
  }
  void lazy_func(const int k, const int a, const int b) {
    {
      dat[k].sum.second =
          dat[k].sum.second * dat[k].lazy.first + dat[k].lazy.second;
    }
  }
  pair<int, ld> connect(const pair<int, ld> l, const pair<int, ld> r) {
    if (l.first == 0 && r.first == 0) {
      return make_pair(0, 0);
    }
    return make_pair(
        l.first + r.first,
        ((l.first * l.second) + (r.first * r.second)) / (r.first + l.first));
  }
  inline void lazy_evaluate_node(int k, int a, int b) {
    lazy_func(k, a, b);
    if (k < N) {
      dat[2 * k].lazy = lazy_connect(dat[2 * k].lazy, dat[k].lazy);
      dat[2 * k + 1].lazy = lazy_connect(dat[2 * k + 1].lazy, dat[k].lazy);
    }
    dat[k].lazy = Zero2;
  }
  inline void update_node(int k) {
    dat[k].sum = connect(dat[2 * k].sum, dat[2 * k + 1].sum);
  }
  void update(int l, int r, pair<ld, ld> v, int k = 1, int a = 0, int b = -1) {
    if (b == -1) b = N;
    if (l < 0 || r < 0) assert(false);
    lazy_evaluate_node(k, a, b);
    if (b <= l || r <= a) return;
    if (l <= a && b <= r) {
      dat[k].lazy = lazy_connect(dat[k].lazy, v);
      lazy_evaluate_node(k, a, b);
      return;
    }
    int m = (a + b) / 2;
    update(l, r, v, 2 * k, a, m);
    update(l, r, v, 2 * k + 1, m, b);
    update_node(k);
  }
  pair<int, ld> get(int l, int r, int k = 1, int a = 0, int b = -1) {
    if (b == -1) b = N;
    if (l < 0 || r < 0) assert(false);
    lazy_evaluate_node(k, a, b);
    if (b <= l || r <= a) return Zero1;
    if (l <= a && b <= r) {
      return dat[k].sum;
    }
    int m = (a + b) / 2;
    pair<int, ld> vl = get(l, r, 2 * k, a, m);
    pair<int, ld> vr = get(l, r, 2 * k + 1, m, b);
    update_node(k);
    return connect(vl, vr);
  }
};
int main() {
  int N, Q;
  cin >> N >> Q;
  lazy_segtree seg(N);
  vector<int> as;
  for (int i = 0; i < N; ++i) {
    seg.dat[seg.N + i].sum = make_pair(1, 0);
  }
  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    seg.update(i, i + 1, make_pair(1, a));
  }
  cout << setprecision(10) << fixed;
  while (Q--) {
    int a;
    cin >> a;
    if (a == 1) {
      int l1, r1, l2, r2;
      cin >> l1 >> r1 >> l2 >> r2;
      l1--;
      l2--;
      auto lp = seg.get(l1, r1);
      auto rp = seg.get(l2, r2);
      auto lsum = lp.first * lp.second;
      auto rsum = rp.first * rp.second;
      seg.update(
          l1, r1,
          make_pair((r1 - l1 - 1) / ld(r1 - l1), rp.second / ld(r1 - l1)));
      seg.update(
          l2, r2,
          make_pair((r2 - l2 - 1) / ld(r2 - l2), lp.second / ld(r2 - l2)));
    } else {
      int l, r;
      cin >> l >> r;
      l--;
      auto p = seg.get(l, r);
      cout << p.first * p.second << endl;
    }
  }
  return 0;
}