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:
/*
Keep solving problems. 
*/

import java.util.*;
import java.io.*;

public class CFA {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    int[] dx = {1, 2, 1, 1};
    int[] dy = {0, 0, -1, 1};

    int[] arr;
    double[] tree;
    double[] mul;
    double[] add;

    void build_tree(int node, int nodeStartIndex, int nodeEndIndex) {
        if(nodeStartIndex > nodeEndIndex) return; // Out of range
        if(nodeStartIndex == nodeEndIndex) { // Leaf node
            tree[node] = arr[nodeStartIndex]; // Init value
            return;
        }

        build_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2); // Init left child
        build_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex); // Init right child
        tree[node] = tree[node * 2] +  tree[node * 2 + 1]; // Init root value
    }

    /**
     * Increment elements within range [queryStartIndex, queryEndIndex] with value
     */
    void update_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex, double multValue, double addValue) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) // Current segment is not within range [i, j]
            return;
        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) { // Segment is fully within range
            tree[node] *= multValue;
            tree[node] += (nodeEndIndex - nodeStartIndex + 1) * addValue;
            mul[node] *= multValue;
            add[node] *= multValue;
            add[node] += addValue;
            return;
        }

        //-------------
        shift(node, nodeStartIndex, nodeEndIndex);
        //-------------
        update_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex, multValue, addValue); // Updating left child
        update_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex, multValue, addValue); // Updating right child

        tree[node] = tree[node * 2] + tree[node * 2 + 1]; // Updating root
    }

    /**
     * Query tree to get max element value within range [queryStartIndex, queryEndIndex]
     */
    double query_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) return 0; // Out of range
        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) // Current segment is totally within range [i, j]
            return tree[node];

        //-------------
        shift(node, nodeStartIndex, nodeEndIndex);
        //-------------
        double q1 = query_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Query left child
        double q2 = query_tree(1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Query right child

        return q1 + q2;
    }

    private void shift(int node, int nodeStartIndex, int nodeEndIndex) {
        tree[node * 2] *= mul[node];
        tree[node * 2 + 1] *= mul[node];
        mul[node * 2] *= mul[node];
        mul[node * 2 + 1] *= mul[node];
        add[node * 2] *= mul[node];
        add[node * 2 + 1] *= mul[node];
        mul[node] = 1.0;
        int mid = (nodeStartIndex + nodeEndIndex) / 2;
        tree[node * 2] += (mid - nodeStartIndex + 1) * add[node];
        tree[node * 2 + 1] += (nodeEndIndex - mid) * add[node];
        add[node * 2] += add[node];
        add[node * 2 + 1] += add[node];
        add[node] = 0;
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void solve() throws IOException {
        int n = nextInt();
        int q = nextInt();
        arr = nextIntArr(n);
        List<Double> res = new ArrayList<>();
        tree = new double[5 * n];
        mul = new double[5 * n];
        add = new double[5 * n];

        Arrays.fill(mul, 1.0);

        build_tree(1, 0, n - 1);

        for (int i = 0; i < q; i++) {
            int t = nextInt();
            if (t == 1) {
                int l1 = nextInt() - 1;
                int r1 = nextInt() - 1;
                int l2 = nextInt() - 1;
                int r2 = nextInt() - 1;

                double avg_val1 = query_tree(1, 0, n - 1, l1, r1) / (r1 - l1 + 1);
                double avg_val2 = query_tree(1, 0, n - 1, l2, r2) / (r2 - l2 + 1);

                update_tree(1, 0, n - 1, l1, r1, 1.0 * (r1 - l1) / (r1 - l1 + 1), avg_val2 / (r1 - l1 + 1));
                update_tree(1, 0, n - 1, l2, r2, 1.0 * (r2 - l2) / (r2 - l2 + 1), avg_val1 / (r2 - l2 + 1));
            }
            else {
                int l = nextInt() - 1;
                int r = nextInt() - 1;

                double tmp = query_tree(1, 0, n - 1, l, r);
                res.add(tmp);
            }
        }

        for (int i = 0; i < res.size(); i++) {
            outln(res.get(i));
        }
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }

    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CFA() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFA();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}