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;
inline long long read() {
  register long long x = 0;
  char zf = 1;
  char ch;
  while (ch != '-' && !isdigit(ch)) ch = getchar();
  if (ch == '-') zf = -1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * zf;
}
void write(long long y) {
  if (y < 0) putchar('-'), y = -y;
  if (y > 9) write(y / 10);
  putchar(y % 10 + 48);
}
void writeln(const long long y) {
  write(y);
  putchar('\n');
}
void bemin(long long &x, const long long y) {
  if (y < x) x = y;
}
void bemax(long long &x, const long long y) {
  if (y > x) x = y;
}
int i, j, k, m, n, x, y, z, cnt;
int v[200010];
struct tree {
  int L, R, len;
  double sum, tag1, tag2;
} a[1600010];
void up(const int x) { a[x].sum = a[x << 1].sum + a[x << 1 | 1].sum; }
void build(const int x, const int L, const int R) {
  a[x].L = L;
  a[x].R = R;
  a[x].tag1 = 1;
  a[x].len = (R - L + 1);
  if (L == R) {
    a[x].sum = v[L];
    return;
  }
  const int mid = L + R >> 1;
  build(x << 1, L, mid);
  build(x << 1 | 1, mid + 1, R);
  up(x);
}
void down(const int x) {
  a[x].sum = a[x].sum * a[x].tag1 + a[x].tag2 * a[x].len;
  a[x << 1].tag1 *= a[x].tag1;
  a[x << 1].tag2 *= a[x].tag1;
  a[x << 1 | 1].tag1 *= a[x].tag1;
  a[x << 1 | 1].tag2 *= a[x].tag1;
  a[x << 1].tag2 += a[x].tag2;
  a[x << 1 | 1].tag2 += a[x].tag2;
  a[x].tag1 = 1;
  a[x].tag2 = 0;
}
double query(const int x, const int L, const int R) {
  down(x);
  down(x << 1);
  down(x << 1 | 1);
  if (a[x].L > R || a[x].R < L) return 0;
  if (a[x].L >= L && a[x].R <= R) return a[x].sum;
  return query(x << 1, L, R) + query(x << 1 | 1, L, R);
}
void change(const int x, const int L, const int R, const double mul,
            const double sum) {
  down(x);
  down(x << 1);
  down(x << 1 | 1);
  if (a[x].L > R || a[x].R < L) return;
  if (a[x].L >= L && a[x].R <= R) {
    const int len = a[x].R - a[x].L + 1;
    a[x].tag1 = a[x].tag1 * mul;
    a[x].tag2 = a[x].tag2 * mul;
    a[x].tag2 += sum;
    down(x);
    return;
  }
  change(x << 1, L, R, mul, sum);
  change(x << 1 | 1, L, R, mul, sum);
  up(x);
}
int main() {
  n = read();
  m = read();
  for (register int i = 1; i <= n; i++) v[i] = read();
  build(1, 1, n);
  while (m--) {
    int opt = read();
    if (opt == 1) {
      const int L1 = read(), R1 = read(), L2 = read(), R2 = read();
      double ans1 = query(1, L1, R1), ans2 = query(1, L2, R2);
      change(1, L1, R1, (double)(R1 - L1) / (R1 - L1 + 1),
             ans2 / (R2 - L2 + 1) / (R1 - L1 + 1));
      change(1, L2, R2, (double)(R2 - L2) / (R2 - L2 + 1),
             ans1 / (R1 - L1 + 1) / (R2 - L2 + 1));
    } else {
      const int L = read(), R = read();
      printf("%.6f\n", query(1, L, R));
    }
  }
  return 0;
}