Eyes Closed

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A type-1 action swaps one uniformly random element from each of two disjoint segments. A type-2 query asks for the expected sum of a range.

Input

The first line contains $n,q$, followed by the initial array. Each action is 1 l1 r1 l2 r2 for two disjoint ranges and a random swap, or 2 l r for an expected range-sum query.

Output

For each type-2 query print a real number; absolute or relative error must not exceed $10^{-4}$.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $2\le n\le10^5$

• $1\le q\le10^5$

• $1\le a_i\le10^9$

• Hai đoạn của thao tác loại 1 không giao nhau.

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.0000000000
3.0000000000

Explanation

After the first random swap, the expected sum of [1,2] is 3. The second random swap also leaves the final queried expectation equal to 3.