406262: GYM102341 A Alakazam

Hello, fellow Pokémon trainer! So you're on a safari as well? It's nice you're here, you were the one to spot an Alakazam colony!

The colony consists of $$$n$$$ Alakazam specimens. Each of them holds a number of spoons increasing their psychic abilities. They've just formed up in a line in order to perform a psychic training. It's not just any kind of training — it's the teleportation training!

The training consists of a number of group teleportations. During each teleportation, a contiguous group of Alakazam specimens disappear and then materialize in the same positions as before, but in a totally random order.

Just before the training, you counted the spoons held by each Alakazam. However, after the training started, you were too far away to count the spoons — you only saw the teleportations. Basing on your observations, can you predict how many spoons are held by Alakazam at some positions in the line throughout the training? Obviously, as the process is random, we're only asking you about the expected number of spoons.

The first line contains two integers $$$n, q$$$ ($$$1 \le n \le 250\,000$$$, $$$1 \le q \le 250\,000$$$) — the number of Alakazam in the line and the number of actions during the training. The following line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the number of spoons held by each specimen in the line.

Each of the next $$$q$$$ lines describes a single action and is in one of the following formats:

• shuffle $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) — the group of Alakazam between the $$$l$$$-th and the $$$r$$$-th specimen (inclusive) teleport and materialize in random order.
• get $$$i$$$ ($$$1 \le i \le n$$$) — you need to predict the expected number of spoons held by the $$$i$$$-th Alakazam in the line.

There will be at least one get query in the file.

For each get query, output a single decimal number: the expected number of spoons held by the specified Alakazam.

Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-9}$$$.

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

1.000000000000
3.000000000000
1.500000000000
2.250000000000

Before the teleportations, Alakazam hold $$$1$$$, $$$2$$$ and $$$3$$$ spoons:

After the first teleportation, two permutations of Alakazam are equally probable: $$$(1, 2, 3)$$$ and $$$(2, 1, 3)$$$. Meanwhile, after both teleportations, the following permutations are equally probable: $$$(1, 2, 3)$$$, $$$(1, 3, 2)$$$, $$$(2, 1, 3)$$$, $$$(2, 3, 1)$$$.