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;
long double values[100005];
int n, q;
struct LazyNode {
  long double p, k;
  LazyNode() {
    k = 0;
    p = 1.0;
  }
  void operator+=(const LazyNode &ln) {
    p *= ln.p;
    k = k * ln.p + ln.k;
  }
};
struct Node {
  long double a, b, x;
  Node() {
    a = 1;
    x = 0;
    b = 0;
  }
  void modify(const LazyNode &ln, int l, int r) {
    a *= ln.p;
    b = ln.p * b + ln.k * (r - l + 1);
  }
  Node join(const Node &other) {
    Node c;
    c.x = getSum() + other.a * other.x + other.b;
    c.a = 1;
    c.b = 0;
    return c;
  }
  long double getSum() { return a * x + b; }
};
struct ST {
  Node T[100005 * 4];
  LazyNode LazyT[100005 * 4];
  int n;
  ST() {}
  ST(int tam) {
    n = tam;
    build_tree(0, 0, n - 1);
  }
  void setSizeAndBuild(int tam) {
    n = tam;
    build_tree(0, 0, n - 1);
  }
  void build_tree(int node, int a, int b) {
    if (a == b) {
      LazyT[node] = LazyNode();
      T[node].x = values[a];
      T[node].a = 1;
      T[node].b = 0;
      return;
    }
    build_tree(((node << 1) + 1), a, ((a + b) >> 1)),
        build_tree(((node << 1) + 2), ((a + b) >> 1) + 1, b);
    T[node] = T[((node << 1) + 1)].join(T[((node << 1) + 2)]);
    LazyT[node] = LazyNode();
  }
  void push(int node, int a, int b) {
    T[node].modify(LazyT[node], a, b);
    if (a != b) {
      LazyT[node * 2 + 1] += LazyT[node];
      LazyT[node * 2 + 2] += LazyT[node];
    }
    LazyT[node] = LazyNode();
  }
  Node query(int node, int a, int b, int lo, int hi) {
    push(node, a, b);
    if (lo > b || a > hi) return Node();
    if (a >= lo && hi >= b) return T[node];
    return query(((node << 1) + 1), a, ((a + b) >> 1), lo, hi)
        .join(query(((node << 1) + 2), ((a + b) >> 1) + 1, b, lo, hi));
  }
  void update(int node, int a, int b, int lo, int hi, const LazyNode &val) {
    push(node, a, b);
    if (lo > b || a > hi) return;
    if (a >= lo && hi >= b) {
      LazyT[node] = val;
      push(node, a, b);
      return;
    }
    update(((node << 1) + 1), a, ((a + b) >> 1), lo, hi, val);
    update(((node << 1) + 2), ((a + b) >> 1) + 1, b, lo, hi, val);
    T[node] = T[((node << 1) + 1)].join(T[((node << 1) + 2)]);
  }
  Node query(int lo, int hi) { return query(0, 0, n - 1, lo, hi); }
  void update(int lo, int hi, const LazyNode &val) {
    update(0, 0, n - 1, lo, hi, val);
  }
} st2;
void showValues() {
  puts("");
  for (int i = 0; i < n; i++) {
    Node val = st2.query(i, i);
    cout << (double)val.getSum() << " ";
  }
  cout << "\n";
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    values[i] = x;
  }
  st2.setSizeAndBuild(n);
  for (int i = 0; i < q; i++) {
    int ty;
    scanf("%d", &ty);
    if (ty == 1) {
      int l1, l2, r1, r2;
      scanf("%d %d", &l1, &r1);
      scanf("%d %d", &l2, &r2);
      l1--;
      r1--;
      l2--;
      r2--;
      int le1 = r1 - l1 + 1;
      int le2 = r2 - l2 + 1;
      Node n1 = st2.query(l1, r1);
      Node n2 = st2.query(l2, r2);
      long double avg1 = n1.getSum() / le1;
      long double avg2 = n2.getSum() / le2;
      long double p1 = (long double)1 / ((long double)le1);
      LazyNode ln1;
      ln1.p = (1 - p1);
      ln1.k = p1 * avg2;
      st2.update(l1, r1, ln1);
      long double p2 = (long double)1 / ((long double)le2);
      LazyNode ln2;
      ln2.p = (1 - p2);
      ln2.k = p2 * avg1;
      st2.update(l2, r2, ln2);
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      l--;
      r--;
      Node node = st2.query(l, r);
      cout << (double)node.getSum() << "\n";
    }
  }
}