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:
/**
 * DA-IICT
 * Author : Savaliya Sagar
 */
import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.fill;
import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Collections.sort;

public class Main
{
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	double tree[],l1[],l2[];
	long a[];
	void solve() throws IOException {
		int n = ni();
		int q = ni();
		a = na(n);
		tree = new double[4*n];
		l1 = new double[4*n];
		l2 = new double[4*n];
		fill(l1,1);
		build(1, 0, n-1);
		while(q-->0) {
			int t = ni();
			if(t==1) {
				int l1 = ni()-1;
				int r1 = ni()-1;
				int l2 = ni()-1;
				int r2 = ni()-1;
				double s1 = query(1, 0, n-1, l1, r1)/(r1-l1+1);
				double s2 = query(1, 0, n-1, l2, r2)/(r2-l2+1);
				update(1,0,n-1,l1,r1,(r1-l1-0.0)/(r1-l1+1),s2/(r1-l1+1));
				update(1,0,n-1,l2,r2,(r2-l2-0.0)/(r2-l2+1),s1/(r2-l2+1));
			}else {
				int l = ni()-1;
				int r = ni()-1;
				out.println(query(1, 0, n-1, l, r));
			}
		}
	}
	
	void build(int node,int start,int end) {
		if(start==end) {
			tree[node] = a[start];
			return;
		}
		int mid = (start+end)/2;
		build(2*node,start,mid);
		build(2*node+1,mid+1,end);
		tree[node] = tree[2*node] + tree[2*node+1];
	}
	
	void update(int node,int start,int end,int l,int r,double m,double c) {
		checklazy(node, start, end);
		if(end<l || start>r) return;
		if(l<=start && end<=r) {
			l1[node] = m;
			l2[node] = c;
			checklazy(node, start, end);
			return;
		}
		int mid = (start+end)/2;
		update(2*node, start, mid, l, r, m, c);
		update(2*node+1, mid+1, end, l, r, m, c);
		tree[node] = tree[2*node] + tree[2*node+1];
	}
	
	double query(int node,int start,int end,int l,int r) {
		checklazy(node, start, end);
		if(end<l || start>r) return 0;
		if(l<=start && end<=r) {
			return tree[node];
		}
		int mid = (start+end)/2;
		double p1 = query(2*node, start, mid, l, r);
		double p2 = query(2*node+1, mid+1, end, l, r);
		return p1+p2;
	}
	
	void checklazy(int node,int l,int r) {
		if(l1[node]!=1 && l2[node]!=0) {
			tree[node] = l1[node]*tree[node]+(r-l+1)*l2[node];
			if(l!=r) {
				l1[2*node] *= l1[node];
				l1[2*node+1] *= l1[node];
				l2[2*node] = l1[node]*l2[2*node] + l2[node];
				l2[2*node+1] = l1[node]*l2[2*node+1] + l2[node];
			}
			l1[node]=1;
			l2[node]=0;
		}
	}
	
	private long[] na(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}

	void run() throws Exception{
		 out = new PrintWriter(System.out);
	     InputStream is = System.in;
		 reader = new BufferedReader(new InputStreamReader(is), 32768);
	     tokenizer = null;
	     solve();
	     out.flush();
	}
	BufferedReader reader;
	StringTokenizer tokenizer;
	public static void main(String[] args) throws Exception{
		new Thread(null, new Runnable(){
			public void run(){
				try{
					new Main().run();
				} catch (Exception e){	e.printStackTrace();}
			}
		}, "1", 1 << 26).start();
	}
	public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    public int ni() { return Integer.parseInt(next()); }
    public long nl() { return Long.parseLong(next());   }
    public Double nd() {  return Double.parseDouble(next());   }
    public String ns() throws IOException{ return reader.readLine();  }
    public void tr(Object... o) { System.out.println(Arrays.deepToString(o));}
}