English · Original
Chinese · Translation
Formal · Original
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.
## 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 _a__i_ (1 ≤ _a__i_ ≤ 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, _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.
[samples]
Vasya 和 Petya 玩腻了学习，于是决定玩一个游戏。游戏开始前，Vasya 会查看一个包含 $n$ 个整数的数组 $a$。一旦他记住了数组 $a$ 的所有元素，游戏就开始。Vasya 闭上眼睛，Petya 执行 $q$ 次操作，每次操作属于以下两种类型之一：
1) Petya 说出四个整数 $l1, r1, l2, r2$ —— 两个不相交区间的边界。之后，他从区间 $[l1, r1]$ 中随机选取一个元素，与从区间 $[l2, r2]$ 中随机选取的另一个元素进行交换。
2) Petya 询问 Vasya 区间 $[l, r]$ 中数组 $a$ 元素的和。
Vasya 是一位数学家，因此他回答的是该区间元素和的数学期望。
你的任务是编写一个程序，像 Vasya 那样回答第二类查询。换句话说，对于每一个第二类查询，你的程序应输出区间 $[l, r]$ 中元素和的数学期望。
第一行包含两个整数 $n, q$ ($2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5$) —— 数组元素个数和需要处理的查询数量。
第二行包含 $n$ 个整数 $a_i$ ($1 ≤ a_i ≤ 10^9$) —— 数组的元素。
接下来的 $q$ 行包含 Petya 的类型 1 或类型 2 的操作。
如果是类型 $1$ 的操作，该行包含 $5$ 个整数 $1, l1, r1, l2, r2$ ($1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n$)。
如果是类型 $2$ 的查询，该行包含 $3$ 个整数 $2, l, r$ ($1 ≤ l ≤ r ≤ n$)。
保证至少存在一个类型 $2$ 的查询，且区间 $[l1, r1]$ 和 $[l2, r2]$ 没有公共元素。
对于每个类型 $2$ 的查询，输出一个实数 —— 区间内元素和的数学期望。
你的答案若绝对误差或相对误差不超过 $10^{-4}$，则被视为正确 —— 即，当 $x$ 为标准答案，$y$ 为你输出的答案时，若满足 $|x - y| \leq 10^{-4} \cdot \max(1, |x|)$，则答案正确。
## Input
第一行包含两个整数 $n, q$ ($2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5$) —— 数组元素个数和需要处理的查询数量。第二行包含 $n$ 个整数 $a_i$ ($1 ≤ a_i ≤ 10^9$) —— 数组的元素。接下来的 $q$ 行包含 Petya 的类型 1 或类型 2 的操作。如果是类型 $1$ 的操作，该行包含 $5$ 个整数 $1, l1, r1, l2, r2$ ($1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n$)。如果是类型 $2$ 的查询，该行包含 $3$ 个整数 $2, l, r$ ($1 ≤ l ≤ r ≤ n$)。保证至少存在一个类型 $2$ 的查询，且区间 $[l1, r1]$ 和 $[l2, r2]$ 没有公共元素。
## Output
对于每个类型 $2$ 的查询，输出一个实数 —— 区间内元素和的数学期望。你的答案若绝对误差或相对误差不超过 $10^{-4}$，则被视为正确 —— 即，当 $x$ 为标准答案，$y$ 为你输出的答案时，若满足 $|x - y| \leq 10^{-4} \cdot \max(1, |x|)$，则答案正确。
[samples]
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the array length and number of queries.
Let $ A = (a_1, a_2, \dots, a_n) $ be the initial array of integers.
Let $ \mathbb{E}[a_i^{(t)}] $ denote the expected value of the element at position $ i $ after $ t $ operations.
**Constraints**
1. $ 2 \le n \le 10^5 $, $ 1 \le q \le 10^5 $
2. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
3. For type-1 queries: $ 1 \le l_1 \le r_1 \le n $, $ 1 \le l_2 \le r_2 \le n $, $ [l_1, r_1] \cap [l_2, r_2] = \emptyset $
4. For type-2 queries: $ 1 \le l \le r \le n $
**Objective**
Process $ q $ queries:
- **Type 1** ($ 1, l_1, r_1, l_2, r_2 $):
Let $ S_1 = [l_1, r_1] $, $ S_2 = [l_2, r_2] $.
Randomly select $ i \in S_1 $, $ j \in S_2 $ uniformly and swap $ a_i \leftrightarrow a_j $.
Update expectations:
$$
\mathbb{E}[a_i^{(t+1)}] = \mathbb{E}[a_i^{(t)}] \cdot \left(1 - \frac{1}{|S_1|}\right) + \frac{1}{|S_2|} \sum_{k \in S_2} \mathbb{E}[a_k^{(t)}] \cdot \frac{1}{|S_1|}, \quad \forall i \in S_1
$$
$$
\mathbb{E}[a_j^{(t+1)}] = \mathbb{E}[a_j^{(t)}] \cdot \left(1 - \frac{1}{|S_2|}\right) + \frac{1}{|S_1|} \sum_{k \in S_1} \mathbb{E}[a_k^{(t)}] \cdot \frac{1}{|S_2|}, \quad \forall j \in S_2
$$
- **Type 2** ($ 2, l, r $):
Output:
$$
\sum_{i=l}^{r} \mathbb{E}[a_i]
$$
API Response (JSON)
{
"problem": {
"name": "E. Eyes Closed",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF895E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vasya 和 Petya 玩腻了学习，于是决定玩一个游戏。游戏开始前，Vasya 会查看一个包含 $n$ 个整数的数组 $a$。一旦他记住了数组 $a$ 的所有元素，游戏就开始。Vasya 闭上眼睛，Petya 执行 $q$ 次操作，每次操作属于以下两种类型之一：\n\n1) Petya 说出四个整数 $l1, r1, l2, r2$ —— 两个不相交区间的边界。之后，他从区间 $[l1, r1]$...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the array length and number of queries. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial array of integers. \nLet $ \\mathbb{E}[a_i^{(t)}] $ de...",
"is_translate": false,
"language": "Formal"
}
]
}