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
import copy
from pprint import pprint
import itertools

def swaps(l1,r1,l2,r2):
	ss = []
	for i in range(l1,r1+1):
		for j in range(l2,r2+1):
			ss.append([i,j])
	return ss

def permute(arr,l1,r1,l2,r2):
	arrays = []
	ss = swaps(l1,r1,l2,r2)
	for a,b in ss:
		temp = copy.deepcopy(arr)
		temp[a],temp[b] = temp[b],temp[a]
		arrays.append(temp)
	return arrays

def asum(arr,l,r):
	temp = 0
	for a in arr:
		temp+= sum(a[l:r+1])
	return temp/len(arr)


n,q = [int(i) for i in input().split()]
arr = [[int(i) for i in input().split()]]

while True:
	newa = []
	stuff = input().split()
	typ,data = stuff[0],stuff[1:]
	if typ == '1':
		l1,r1,l2,r2 = [int(i)-1 for i in data]
		for a in arr:
			newa += permute(a,l1,r1,l2,r2)
		arr = newa
		arr.sort()
		arr = list(k for k,_ in itertools.groupby(arr))

	elif typ == '2':
		l,r = [int(i)-1 for i in data]
		print(asum(arr,l,r))





		    	     		  	  	 		 		  	