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

public class E895 {

	int n;
	double[] a;

	private void solve() throws Exception {
		n = nextInt();
		int nn = n;
		int size = 2;
		while(nn > 0) {
			nn/=2;
			size*=2;
		}
		int q = nextInt();
		a = new double[n];
		tree = new double[size];
		lazySum = new double[size];
		lazyProduct = new double[size];
		Arrays.fill(lazyProduct, 1);
		updated = new boolean[size];
		Arrays.fill(updated, true);
		for(int i = 0; i < n; i++) a[i] = nextLong();
		build(1,0,n-1);for(int j = 0; j < q; j++){
			if(nextInt() == 1){
				int l1 = nextInt()-1;
				int r1 = nextInt()-1;
				int l2 = nextInt()-1;
				int r2 = nextInt()-1;
				int n1 = r1-l1+1;
				int n2 = r2-l2+1;
				double mean1 = queryRange(1,0,n-1,l1,r1)/n1;
				double mean2 = queryRange(1,0,n-1,l2,r2)/n2;
				updateRange(1,0,n-1, l1, r1, mean2/n1, (n1-1)/(double)n1);
				updateRange(1,0,n-1, l2, r2, mean1/n2, (n2-1)/(double)n2);
			}else{
				int l = nextInt()-1;
				int r = nextInt()-1;
				out.println(queryRange(1,0,n-1,l,r));
			}
		}
	}

	double[] tree;
	boolean[] updated;
	double[] lazySum;
	double[] lazyProduct;

	void build(int node, int start, int end) {
		if(start == end) {
			// Leaf node will have a single element
			tree[node] = a[start];
		}else{
			int mid = (start + end) / 2;
			// Recurse on the left child
			build(2*node, start, mid);
			// Recurse on the right child
			build(2*node+1, mid+1, end);
			// Internal node will have the sum of both of its children
			tree[node] = tree[2*node] + tree[2*node+1];
		}
	}
	
	void updateRange(int node, int start, int end, int l, int r, double sum, double product) {
	    if(!updated[node]) { 
	        // This node needs to be updated
	    	tree[node] = tree[node] * lazyProduct[node] + (end - start + 1) *lazySum[node];            // Update it
	        if(start != end) {
	        	lazyUpdate(node*2, lazySum[node], lazyProduct[node]);                  // Mark child as lazy
	        	lazyUpdate(node*2+1, lazySum[node], lazyProduct[node]);                  // Mark child as lazy	            
	        }
	        lazyReset(node);                                  // Reset it
	    }
	    if(start > end || start > r || end < l)              // Current segment is not within range [l, r]
	        return;
	    if(start >= l && end <= r) {			// Segment is fully within range
	        tree[node] = tree[node] * product + (end - start + 1) * sum;
	        if(start != end) {					// Not leaf node
	        	lazyUpdate(node*2, sum, product);
	        	lazyUpdate(node*2+1, sum, product);
	        }
	        return;
	    }
	    int mid = (start + end) / 2;
	    updateRange(node*2, start, mid, l, r, sum, product);        // Updating left child
	    updateRange(node*2 + 1, mid + 1, end, l, r, sum, product);   // Updating right child
	    tree[node] = tree[node*2] + tree[node*2+1];        // Updating root with max value 
	}

	double queryRange(int node, int start, int end, int l, int r) {
	    if(start > end || start > r || end < l)
	        return 0;         // Out of range
	    if(!updated[node]) {
	        // This node needs to be updated
	        tree[node] = tree[node] * lazyProduct[node] + (end - start + 1) *lazySum[node];            // Update it
	        if(start != end) {
	        	lazyUpdate(node*2, lazySum[node], lazyProduct[node]);	// Mark child as lazy
	        	lazyUpdate(node*2+1, lazySum[node], lazyProduct[node]);	// Mark child as lazy
	        }
	        lazyReset(node);                 // Reset it
	    }
	    if(start >= l && end <= r)             // Current segment is totally within range [l, r]
	        return tree[node];
	    int mid = (start + end) / 2;
	    double p1 = queryRange(node*2, start, mid, l, r);         // Query left child
	    double p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
	    return (p1 + p2);
	}
	
	void lazyReset(int node){
		updated[node] = true;
		lazySum[node] = 0;
		lazyProduct[node] = 1;
	}
	
	void lazyUpdate(int node, double sum, double product){
		updated[node] = false;
		lazyProduct[node] *= product;
		lazySum[node] = lazySum[node]*product+sum;
	}


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

	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer tokenizer;

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private float nextFloat() throws IOException {
		return Float.parseFloat(nextToken());
	}

	private String nextLine() throws IOException {
		return new String(in.readLine());
	}

	private String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(in.readLine());
		}
		return tokenizer.nextToken();
	}


}