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>
struct sgt {
  struct node {
    int l, r;
    double addtag, multag, s;
  };
  node a[5000005];
  double f[100005];
  int n;

 private:
  void pushup(int k) { a[k].s = a[k * 2].s + a[k * 2 + 1].s; }
  void tagclear(int k) {
    a[k].addtag = 0;
    a[k].multag = 1;
  }
  void putadd(int k, double v) {
    a[k].addtag = a[k].addtag + v;
    a[k].s = a[k].s + v * (a[k].r - a[k].l + 1);
  }
  void putmul(int k, double v) {
    a[k].multag = a[k].multag * v;
    a[k].addtag = a[k].addtag * v;
    a[k].s = a[k].s * v;
  }
  void pushdown(int k) {
    putmul(k * 2, a[k].multag), putadd(k * 2, a[k].addtag);
    putmul(k * 2 + 1, a[k].multag), putadd(k * 2 + 1, a[k].addtag);
    tagclear(k);
  }
  void build(int k, int l, int r) {
    tagclear(k);
    a[k].l = l, a[k].r = r;
    if (l == r) return a[k].s = f[l], void();
    int mid = (l + r) / 2;
    build(k * 2, l, mid);
    build(k * 2 + 1, mid + 1, r);
    pushup(k);
  }
  void updadd(int k, int x, int y, double v) {
    if (x <= a[k].l && a[k].r <= y) return putadd(k, v), void();
    int mid = (a[k].l + a[k].r) / 2;
    pushdown(k);
    if (x <= mid) updadd(k * 2, x, y, v);
    if (mid < y) updadd(k * 2 + 1, x, y, v);
    pushup(k);
  }
  void updmul(int k, int x, int y, double v) {
    if (x <= a[k].l && a[k].r <= y) return putmul(k, v), void();
    int mid = (a[k].l + a[k].r) / 2;
    pushdown(k);
    if (x <= mid) updmul(k * 2, x, y, v);
    if (mid < y) updmul(k * 2 + 1, x, y, v);
    pushup(k);
  }
  double query(int k, int x, int y) {
    if (x <= a[k].l && a[k].r <= y) return a[k].s;
    int mid = (a[k].l + a[k].r) / 2;
    double ans = 0;
    pushdown(k);
    if (x <= mid) ans = ans + query(k * 2, x, y);
    if (mid < y) ans = ans + query(k * 2 + 1, x, y);
    return ans;
  }

 public:
  void make(int nn) {
    n = nn;
    build(1, 1, n);
  }
  void add(int l, int r, double k) { updadd(1, l, r, k); }
  void mul(int l, int r, double k) { updmul(1, l, r, k); }
  double ask(int l, int r) { return query(1, l, r); }
};
sgt t;
int n, q;
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%lf", &t.f[i]);
  t.make(n);
  while (q--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int l1, r1, l2, r2, len1, len2;
      scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
      len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
      double x1 = t.ask(l1, r1), x2 = t.ask(l2, r2);
      t.mul(l1, r1, (len1 - 1) / (double)len1), t.add(l1, r1, x2 / len2 / len1);
      t.mul(l2, r2, (len2 - 1) / (double)len2), t.add(l2, r2, x1 / len1 / len2);
    } else if (opt == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%lf\n", t.ask(l, r));
    }
  }
  return 0;
}