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.math.*;
import java.util.*;
import java.io.*;

public class Main {
class Node {
    double a;
    double b;
    public Node(double a,double b){
        this.a=a;
        this.b=b;
    }
}
    void solve(){
        int n=ni(),q=ni();
        a=new int[n+1];
        for(int i=1;i<=n;i++) a[i]=ni();
        tree=new double[4*n+1];
        lazy=new Node[4*n+1];

        build(1,1,n);
        while(q-->0){
            int t=ni();
            if(t==1){
                int l1=ni(),r1=ni(),l2=ni(),r2=ni();
                double sum1=querry(1,l1,r1,1,n),sum2=querry(1,l2,r2,1,n);
                double p1=r1-l1+1,p2=(r2-l2+1);
                update(1,l1,r1,1,n,(p1-1)/p1,(sum2)/(p1*p2));
                update(1,l2,r2,1,n,(p2-1)/p2,(sum1)/(p1*p2));

            }else {
                int l=ni(),r=ni();
                double ans=querry(1,l,r,1,n);
                pw.println(ans);
            }
        }

    }
    double tree[];
    int a[];
    Node lazy[];
    void build(int id,int l,int r){
        lazy[id]=new Node(1,0);
      if(l==r){
          tree[id]=a[l];
      }else {
          int mid=(l+r)/2;
          build(2*id,l,mid);
          build(2*id+1,mid+1,r);
          tree[id]=tree[2*id]+tree[2*id+1];
      }
    }
    void update(int id,int x,int y,int l,int r,double a,double b){

            if(lazy[id].b>1e-6) {
                tree[id] = (lazy[id].a) * tree[id] + lazy[id].b * (r - l + 1);
                if (l != r) {

                      lazy[2*id].a*=lazy[id].a;
                      lazy[2*id].b=lazy[2 * id].b * lazy[id].a + lazy[id].b;
                    lazy[2*id+1].a*=lazy[id].a;
                    lazy[2*id+1].b=lazy[2 * id+1].b * lazy[id].a + lazy[id].b;
                }
                lazy[id] = new Node(1, 0);
            }
        if(r<x || l>y) return;

        if(x<=l && r<=y){
            tree[id]=a*tree[id]+(r-l+1)*b;
            if(l!=r){
                lazy[2*id]=new Node(lazy[2*id].a*a,lazy[2*id].b*a+b);
                lazy[2*id+1]=new Node(lazy[2*id+1].a*a,lazy[2*id+1].b*a+b);

            }
            return;
        }
        int mid=(l+r)/2;
        update(2*id,x,y,l,mid,a,b);
        update(2*id+1,x,y,mid+1,r,a,b);
        tree[id]=tree[2*id]+tree[2*id+1];
    }
    double querry(int id,int x,int y,int l,int r){

        if(lazy[id].b>1e-6) {
            tree[id] = (lazy[id].a) * tree[id] + lazy[id].b * (r - l + 1);
            if (l != r) {

                lazy[2*id].a*=lazy[id].a;
                lazy[2*id].b=lazy[2 * id].b * lazy[id].a + lazy[id].b;
                lazy[2*id+1].a*=lazy[id].a;
                lazy[2*id+1].b=lazy[2 * id+1].b * lazy[id].a + lazy[id].b;
            }
            lazy[id] = new Node(1, 0);
        }
        if(r<x || l>y) return 0;
        if(x<=l && r<=y) return tree[id];
        int mid=(l+r)/2;
        return querry(2*id,x,y,l,mid)+querry(2*id+1,x,y,mid+1,r);
    }


    long M=(long)1e9+7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";
    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }

    public static void main(String[] args) throws Exception { new Main().run(); }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private void tr(Object... o) { if(INPUT.length() > 0)System.out.println(Arrays.deepToString(o)); }
}