题目描述

ak机最近学习了连通器原理：在连通器中装有同种液体，当连通器中液体不流动时，各容器中液面总保持相平。

ak机有$nn$支规格相同的试管，这些试管中有一些底部是相互连通的。

为了避免混淆试管之间的连通性，ak机给每支试管做了标记，第$i$支试管的标记为$t_i$。如果两支试管标记相同，那么它们就是联通的。

初始时，每支试管中都没有水，并且视试管的容积为无穷大，现在ak机有三种操作：

操作1：$1\;\;a\;\;b$表示这是个注水操作，表示ak机向第$a$支试管中注入$b$毫升水。

操作2：$2\;\;a\;\;b$表示这是个抽水操作，表示ak机从第$a(1\le a\le n)$支试管中抽出$b(1\le b\le 10^4)$毫升水，该操作保证第$a$支试管所在的连通器中至少有$b$毫升水。

操作3：$3\;\;a$表示这是个询问操作，ak机想知道第$a$支试管中有多水毫升水。

他会进行$m$个操作，你能帮ak机完成这些操作吗？

由于试管的规格相同，因此忽略掉底部连通部分的体积，我们可以进一步简化连通器原理：在连通器中装有同种液体，当连通器中液体不流动时，各容器中的液体体积相同。

输入描述

第一行给出两个整数$n,m(1\le n,m\le 10^5)$，分别表示试管数量和操作数量。

第二行给出$n$个整数，第$i$个整数表示第$i$试管的标签$t_i(1\le t_i\le n)$。

接下来$m$行，每行都是一个操作，其格式如题目所述。

输出描述

对于每个$3$操作，输出一个浮点数，表示询问的试管中水的体积。

假设正确答案为$a$，你输出的答案为$b$，当$\frac{\mid a-b\mid}{max(a,1)}<10^{-5}$ 时视为答案正确。

样例1

输入

5 6
1 2 1 2 3
1 1 5
3 1
1 2 7
3 4
2 4 4
3 2

输出

2.500000
3.500000
1.500000

样例解释

由$t$值我们知道：第$1$支试管和第$3$支试管连通，第$2$支试管和第$4$支试管连通。

第一个操作我们向第$1$支试管中注入$5$毫升水，根据连通器原理，最终第$1$支试管和第$3$支试管中的水是一样的，即$\frac{5}{2} = 2.5$毫升。

同理，第三个操作最终会使得第$2$支试管和第$4$支试管中的水都是$\frac{7}{2} =3.5$毫升。

抽水操作也是相同的道理。

需要注意的是，虽然直观地看第$4$支试管中此时只有$3.5$毫升水，但是第$4$支试管所在的整个连通器中有$7$毫升水，因此ak机是可以抽取$4$毫升水的。

样例2

输入

6 8
1 2 2 2 3 1
1 3 10
3 2
2 3 2
3 3
1 1 9
1 5 10
3 5
3 6

输出

3.333333
2.666667
10.000000
4.500000