Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Eyes Closed

time limit per test

2.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya 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.

Input

The first line contains two integers *n*, *q* (2 ≤ *n* ≤ 10^{5}, 1 ≤ *q* ≤ 10^{5}) — the number of elements in the array and the number of queries you need to handle.

The second line contains *n* integers *a*_{i} (1 ≤ *a*_{i} ≤ 10^{9}) — 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.

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 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2018 11:21:43 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|