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 *l*1, *r*1, *l*2, *r*2 — boundaries of two non-intersecting segments. After that he swaps one random element from the [*l*1, *r*1] segment with another random element from the [*l*2, *r*2] 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.
The first line contains two integers *n*, *q* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>, 1 ≤ *q* ≤ 10<sup class="upper-index">5</sup>)  — the number of elements in the array and the number of queries you need to handle.

The second line contains *n* integers *a*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>)  — 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, *l*1, *r*1, *l*2, *r*2 (1 ≤ *l*1 ≤ *r*1 ≤ *n*, 1 ≤ *l*2 ≤ *r*2 ≤ *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 [*l*1, *r*1], [*l*2, *r*2] don't have common elements.
none
#include <bits/stdc++.h>
using namespace std;

struct info{
	double ans , sum , mul;
	info(){
		ans = sum = 0.0;
		mul = 1.0;
	}
};

const int N = 2e5 + 5;
info seg[N << 2];
int arr[N] , n , q , cnt;

void build(int ver , int left , int right){
	if(left + 1 == right){
		seg[ver].ans = arr[left];
		return;
	}

	int mid = (right + left) >> 1;
	build(ver << 1 , left , mid);
	build(ver << 1 | 1 , mid , right);
	seg[ver].ans = seg[ver << 1].ans + seg[ver << 1 | 1].ans;
}

void shift(int ver , int left , int right){
	if(left + 1 == right) return;
	int mid = (right + left) >> 1;
	double len1 = mid - left , len2 = right - mid;
	seg[ver << 1].ans *= seg[ver].mul;
	seg[ver << 1].mul *= seg[ver].mul;
	seg[ver << 1].sum *= seg[ver].mul;
	seg[ver << 1].ans += seg[ver].sum * len1;
	seg[ver << 1].sum += seg[ver].sum;
	seg[ver << 1 | 1].ans *= seg[ver].mul;
	seg[ver << 1 | 1].mul *= seg[ver].mul;
	seg[ver << 1 | 1].sum *= seg[ver].mul;
	seg[ver << 1 | 1].ans += seg[ver].sum * len2;
	seg[ver << 1 | 1].sum += seg[ver].sum;
	seg[ver].mul = 1.0;
	seg[ver].sum = 0.0;
}

void update(int ver , int left , int right , int l , int r , double zarb , double jam){
	if(right <= l || r <= left)
		return;

	if(left >= l && right <= r){
		seg[ver].ans *= zarb;
		seg[ver].mul *= zarb;
		seg[ver].sum *= zarb;
		seg[ver].ans += (double)(right - left) * jam;
		seg[ver].sum += jam;
		return;
	}

	shift(ver , left , right);
	int mid = (right + left) >> 1;
	update(ver << 1 , left , mid , l , r , zarb , jam);
	update(ver << 1 | 1 , mid , right , l , r , zarb , jam);
	seg[ver].ans = seg[ver << 1].ans + seg[ver << 1 | 1].ans;
}

double get(int ver , int left , int right , int l , int r){
	if(right <= l || r <= left)
		return 0.0;

	if(left >= l && right <= r)
		return seg[ver].ans;

	shift(ver , left , right);
	int mid = (right + left) >> 1;
	return get(ver << 1 , left , mid , l , r) + get(ver << 1 | 1 , mid , right , l , r);
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for(int i = 0 ; i < n ; i++)
		cin >> arr[i];

	build(1 , 0 , n);

	while(q--){
		cnt++;
		int type;
		cin >> type;
		if(type == 1){
			int l1 , r1 , l2 , r2;
			cin >> l1 >> r1 >> l2 >> r2;
			l1--;
			l2--;
			double len1 = r1 - l1 , len2 = r2 - l2;
			double A = get(1 , 0 , n , l1 , r1);
			double B = get(1 , 0 , n , l2 , r2);
			double mul1 = (len1 - 1) / len1;
			double mul2 = (len2 - 1) / len2;
			B /= (len1 * len2);
			A /= (len1 * len2);
			update(1 , 0 , n , l1 , r1 , mul1 , B);
			update(1 , 0 , n , l2 , r2 , mul2 , A);
		}
		else{
			int l , r;
			cin >> l >> r;
			l--;
			cout << setprecision(6) << fixed << get(1 , 0 , n , l , r) << '\n';
		}
	}
	return 0;
}