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;
vector<long double> ds;
vector<vector<pair<int, int> > > es;
vector<bool> bolo;
vector<pair<int, int> > dynamic_minu_ones;
vector<int> pocet_hran;
vector<int> to_remove;
int n, m, x, k;
bool da_sa = true;
int binar(int l, int r, int c) {
  int s = (l + r) / 2;
  if (r - l == 1) {
    return l;
  }
  if (ds[s] == c) {
    return binar(s, r, c);
  } else {
    return binar(l, s, c);
  }
}
struct node {
  long double average = 0;
  long double left_average_update = 0;
  long double left_average_weight = 0;
  int l = 0;
  int r = 0;
};
vector<node> tree;
int size_of_tree = 1;
long double find_sum(int index) {
  return tree[index].average * (tree[index].r - tree[index].l);
}
void build_tree(int v, int l, int r) {
  tree[v].l = l;
  tree[v].r = r;
  if (r - l == 1) {
    if (l < n)
      tree[v].average = ds[l];
    else
      tree[v].average = 0;
  } else {
    int s = (l + r) / 2;
    build_tree(v * 2, l, s);
    build_tree(v * 2 + 1, s, r);
    tree[v].average = find_sum(v * 2) + find_sum(v * 2 + 1);
    tree[v].average /= (tree[v].r - tree[v].l);
  }
}
void push_left_deeper(int index, node& v);
void update(int v, long double a, long double w) {
  tree[v].average =
      (tree[v].average * (tree[v].r - tree[v].l) + w * (a - tree[v].average)) /
      (tree[v].r - tree[v].l);
  if (tree[v].r - tree[v].l == 1) return;
  if (w == 0) return;
  if (tree[v].left_average_weight > 0) {
    long double old_update = tree[v].left_average_update;
    long double old_weight = tree[v].left_average_weight;
    long double overlapping_p =
        (1.0 / (tree[v].r - tree[v].l)) * w * old_weight;
    long double not_overlapping_p_both_present =
        ((tree[v].r - tree[v].l - 1.0) / (tree[v].r - tree[v].l)) * w *
        old_weight;
    long double zmeni_sa = (1 - old_weight) * w + (1 - w) * old_weight +
                           (overlapping_p) + not_overlapping_p_both_present * 2;
    tree[v].left_average_update = (1 - w) * old_weight * old_update;
    tree[v].left_average_update += (1 - old_weight) * w * a;
    tree[v].left_average_update += overlapping_p * a;
    tree[v].left_average_update +=
        not_overlapping_p_both_present * (a + old_update);
    tree[v].left_average_update /= zmeni_sa;
    tree[v].left_average_weight = zmeni_sa;
    do {
      if (0)
        std::cerr << "w * old_weight"
                  << ": " << w * old_weight << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "old_weight"
                  << ": " << old_weight << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "(tree[v].r - tree[v].l - 1) / (tree[v].r - tree[v].l)"
                  << ": "
                  << (tree[v].r - tree[v].l - 1) / (tree[v].r - tree[v].l)
                  << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "w"
                  << ": " << w << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "v"
                  << ": " << v << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "tree[v].l"
                  << ": " << tree[v].l << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "tree[v].r"
                  << ": " << tree[v].r << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "overlapping_p"
                  << ": " << overlapping_p << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "not_overlapping_p_both_present"
                  << ": " << not_overlapping_p_both_present << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "zmeni_sa"
                  << ": " << zmeni_sa << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "(a * w + old_update * old_weight) / (w + old_weight)"
                  << ": "
                  << (a * w + old_update * old_weight) / (w + old_weight)
                  << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "tree[v].left_average_weight"
                  << ": " << tree[v].left_average_weight << std::endl;
    } while (0);
    do {
      if (0)
        std::cerr << "tree[v].left_average_update"
                  << ": " << tree[v].left_average_update << std::endl;
    } while (0);
  } else {
    tree[v].left_average_weight = w;
    tree[v].left_average_update = a;
  }
}
void push_left_deeper(int index, node& v) {
  update(index * 2, v.left_average_update, v.left_average_weight / 2);
  update(index * 2 + 1, v.left_average_update, v.left_average_weight / 2);
  v.left_average_update = 0;
  v.left_average_weight = 0;
}
long double find_sum(int l, int r, int v) {
  if (l <= tree[v].l && tree[v].r <= r) return find_sum(v);
  if (l >= tree[v].r || r <= tree[v].l) return 0;
  push_left_deeper(v, tree[v]);
  return find_sum(l, r, v * 2) + find_sum(l, r, v * 2 + 1);
}
void add_number(int l, int r, int v, long double c) {
  if (l <= tree[v].l && tree[v].r <= r) {
    long double w = (tree[v].r - tree[v].l) / (long double)(r - l);
    update(v, c, w);
    return;
  }
  if (l >= tree[v].r || r <= tree[v].l) return;
  push_left_deeper(v, tree[v]);
  add_number(l, r, v * 2, c);
  add_number(l, r, v * 2 + 1, c);
  tree[v].average = (tree[v * 2].average + tree[v * 2 + 1].average) / 2;
}
int main() {
  int q;
  cin >> n >> q;
  ds.resize(n);
  for (int i = 0; i < (n); i++) {
    cin >> ds[i];
  }
  size_of_tree = 1;
  while (size_of_tree < n) {
    size_of_tree *= 2;
  }
  size_of_tree *= 2;
  tree.resize(size_of_tree);
  build_tree(1, 0, size_of_tree / 2);
  int id, l1, l2, r1, r2;
  for (int i = 0; i < (q); i++) {
    cin >> id >> l1 >> l2;
    if (id == 1) {
      cin >> r1 >> r2;
      long double sum_l = find_sum(l1 - 1, l2, 1);
      long double average_l = sum_l / (long double)(l2 - l1 + 1);
      long double sum_r = find_sum(r1 - 1, r2, 1);
      long double average_r = sum_r / (long double)(r2 - r1 + 1);
      add_number(l1 - 1, l2, 1, average_r);
      add_number(r1 - 1, r2, 1, average_l);
    } else if (id == 2) {
      cout << setprecision(10) << find_sum(l1 - 1, l2, 1) << endl;
    }
  }
  return 0;
}