你好，宝可梦训练师！你也在进行狩猎吗？很高兴见到你，你竟然发现了一个胡地（Alakazam）族群！

这个族群由 $n$ 只胡地组成。每只胡地都持有一定数量的勺子，这些勺子能增强它们的超能力。它们刚刚排成一列，准备进行超能力训练。这可不是普通的训练，而是瞬间移动训练！

训练包含多次群体瞬间移动。在每次瞬间移动中，一段连续的胡地会消失，然后以完全随机的顺序出现在原来的位置上。

在训练开始前，你数了每只胡地持有的勺子数量。然而，训练开始后，由于你离得太远，无法数清勺子的数量——你只能观察到瞬间移动的过程。基于你的观察，你能预测训练过程中队列中某些位置的胡地持有的勺子数量吗？显然，由于过程是随机的，我们只要求你计算勺子数量的期望值。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n \le 250\,000, 1 \le q \le 250\,000$)，分别表示队列中胡地的数量和训练过程中的操作次数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)，表示队列中每只胡地持有的勺子数量。

接下来的 $q$ 行，每行描述一个操作，格式如下：

• shuffle l r ($1 \le l \le r \le n$) —— 第 $l$ 只到第 $r$ 只胡地（包含两端）组成的群体进行瞬间移动，并以随机顺序重新排列。
• get i ($1 \le i \le n$) —— 你需要预测第 $i$ 只胡地持有的勺子数量的期望值。

文件中至少包含一个 get 查询。

输出格式

对于每个 get 查询，输出一个十进制数：指定胡地持有勺子数量的期望值。如果你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

样例

输入 1

3 6
1 2 3
get 1
get 3
shuffle 1 2
shuffle 2 3
get 1
get 3

输出 1

1.000000000000
3.000000000000
1.500000000000
2.250000000000

说明

在瞬间移动之前，胡地持有的勺子数量分别为 1, 2 和 3：

在第一次瞬间移动后，胡地的两种排列方式概率相等：$(1, 2, 3)$ 和 $(2, 1, 3)$。同时，在两次瞬间移动后，以下排列方式概率相等：$(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1)$。