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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Asgar Javadov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        FastWriter out = new FastWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, InputReader in, FastWriter out) {
            int n = in.nextInt();
            int q = in.nextInt();
            int[] a = in.readIntArray(n);

            TaskE.SegmentTreeLazy tree = new TaskE.SegmentTreeLazy(a);

            while (--q >= 0) {
                int type = in.nextInt();
                if (type == 1) {
                    int l1 = in.nextInt() - 1;
                    int r1 = in.nextInt() - 1;
                    int l2 = in.nextInt() - 1;
                    int r2 = in.nextInt() - 1;
                    double x = tree.mean(l1, r1);
                    double y = tree.mean(l2, r2);

                    tree.update(l1, r1, y);
                    tree.update(l2, r2, x);
                } else {
                    int l = in.nextInt() - 1;
                    int r = in.nextInt() - 1;
                    out.println(tree.get(l, r));
                }
            }
        }

        static class SegmentTreeLazy {
            int n;
            double[] tree;
            double[] factor;
            double[] add;

            public SegmentTreeLazy(int[] a) {
                this.n = a.length;
                int sz = Integer.highestOneBit(n) << 2;
                this.tree = new double[sz];
                this.factor = new double[sz];
                this.add = new double[sz];
                buildTree(1, 0, n - 1, a);
            }

            private void buildTree(int node, int l, int r, int[] a) {
                if (l > r) return;

                factor[node] = 1D;
                add[node] = 0D;

                if (l == r) {
                    tree[node] = (double) a[l];
                    return;
                }

                int mid = l + r >> 1;
                buildTree(node << 1, l, mid, a);
                buildTree(node << 1 | 1, mid + 1, r, a);

                tree[node] = tree[node << 1] + tree[node << 1 | 1];
            }

            public double get(int l, int r) {
                return get(1, 0, n - 1, l, r);
            }

            public double mean(int l, int r) {
                return get(l, r) / (r - l + 1);
            }

            private double get(int node, int l, int r, int s, int e) {
                if (l > r || r < s || e < l) return 0D;

                if (factor[node] != 1D || add[node] != 0D) {
                    tree[node] = tree[node] * factor[node] + (r - l + 1) * add[node];

                    if (l != r) {
                        int left = node << 1;
                        int right = node << 1 | 1;

                        factor[left] *= factor[node];
                        factor[right] *= factor[node];

                        add[left] = add[left] * factor[node] + add[node];
                        add[right] = add[right] * factor[node] + add[node];
                    }
                    factor[node] = 1D;
                    add[node] = 0D;
                }

                if (s <= l && r <= e) {
                    return tree[node];
                }

                int mid = l + r >> 1;
                return get(node << 1, l, mid, s, e) + get(node << 1 | 1, mid + 1, r, s, e);
            }

            public void update(int qs, int qe, double x) {
                double scale = (qe - qs) / (double) (qe - qs + 1);
                x /= (qe - qs + 1);
                update(1, 0, n - 1, qs, qe, scale, x);
            }

            private void update(int node, int l, int r, int qs, int qe, double scale, double x) {
                if (l > r || r < qs || qe < l) return;

                if (qs <= l && r <= qe) {
                    factor[node] *= scale;
                    add[node] = add[node] * scale + x;

                    tree[node] = tree[node] * factor[node] + add[node] * (r - l + 1);
                    if (l != r) {
                        int left = node << 1;
                        factor[left] *= factor[node];
                        add[left] = add[left] * factor[node] + add[node];

                        int right = node << 1 | 1;
                        factor[right] *= factor[node];
                        add[right] = add[right] * factor[node] + add[node];
                    }
                    factor[node] = 1D;
                    add[node] = 0D;
                    return;
                }

                int m = l + r >> 1;
                update(node << 1, l, m, qs, qe, scale, x);
                update(node << 1 | 1, m + 1, r, qs, qe, scale, x);
                computeAndPropagate(node << 1, l, m);
                computeAndPropagate(node << 1 | 1, m + 1, r);
                tree[node] = tree[node << 1] + tree[node << 1 | 1];
            }

            private void computeAndPropagate(int node, int l, int r) {
                if (factor[node] != 1D || add[node] != 0D) {
                    tree[node] = tree[node] * factor[node] + (r - l + 1) * add[node];

                    if (l != r) {
                        int left = node << 1;
                        int right = node << 1 | 1;

                        factor[left] *= factor[node];
                        factor[right] *= factor[node];

                        add[left] = add[left] * factor[node] + add[node];
                        add[right] = add[right] * factor[node] + add[node];
                    }
                    factor[node] = 1D;
                    add[node] = 0D;
                }
            }

        }

    }

    static class InputReader extends BufferedReader {
        StringTokenizer tokenizer;

        public InputReader(InputStream inputStream) {
            super(new InputStreamReader(inputStream), 32768);
        }

        public InputReader(String filename) {
            super(new InputStreamReader(Thread.currentThread().getContextClassLoader().getResourceAsStream(filename)));
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(readLine());
                } catch (IOException e) {
                    throw new RuntimeException();
                }
            }
            return tokenizer.nextToken();
        }

        public Integer nextInt() {
            return Integer.valueOf(next());
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
                array[i] = nextInt();
            return array;
        }

    }

    static class FastWriter extends PrintWriter {
        public FastWriter(OutputStream outputStream) {
            super(outputStream);
        }

        public FastWriter(Writer writer) {
            super(writer);
        }

        public FastWriter(String filename) throws FileNotFoundException {
            super(filename);
        }

    }
}