桑泽打完了一场比赛，荣获了四等奖。他感到了世界的参差，于是他收收心，找了个元宇宙电子厂上班

该电子厂生产电子白茶。一开始流水线上有 n 罐茶，生产编号从 1 开始递增。编号为 i 的茶质量指标为 p_i

桑泽负责质检，他需要随时汇报当前所有茶质量指标的标准差 s ，对长为 m 的数组 a ，下标从 1 开始，则标准差计算公式为： \overline a=\dfrac1m\sum_{i=1}^ma_i\quad,s=\sqrt{\dfrac1m\sum_{i=1}^m (a_i-\overline a)^2} 然而流水线是变化的，经常会发生下面三种操作：

1. 在流水线队尾增加一罐茶，编号 j 为当前最大编号 +1
2. 取走流水线上编号最小的一罐茶
3. 重新加工编号为 j 的茶，更改其质量指标 p_j

每次操作结束后，桑泽都需要汇报流水线上所有茶质量指标的标准差，请你帮他完成这个任务

输入一行两个整数 n,m(1\le n,m\le10^5) ，代表初始茶的罐数和操作次数

接下来输入一行 n 个整数，第 i 个整数代表 p_i(1\le p_i\le10^5)

接下来输入 m 行，每行的输入格式为下面三者之一：

• 两个整数 1 w ，代表执行操作 1 ，且增加的茶质量指标为 w
• 一个整数 2 ，代表执行操作 2
• 三个整数 3 x y ，代表执行操作 3 ，将编号为 x 的茶质量指标更改为 y

保证 1\le w,y\le10^5 且编号为 x 的茶一定在流水线上；保证执行任何操作后流水线上至少有一罐茶

输出 m 行，每行一个实数 r_i，代表第 i 次操作后流水线上所有茶质量指标的标准差

你的答案被视为是正确的当且仅当你的答案与标准答案的绝对误差不超过 10^{-2}

提示1:若你认为你的代码无误且复杂度正确，请检查是否有爆 int (请参考 一鸣师姐的粤语课)，下标或长度不正确等问题；特别地，本题有可能会爆 long long，请你在你认为将要爆 long long 的时候将其转化为 __int128 或 double

提示2:当你过了 8 个测试点还剩一个没过时，请考虑常数列样例

提示3:由于浮点误差，可能会出现 x-x < 0 ，从而使得开方失败出现 nan

提示4:请使用较为快速的读入和输出方式，建议不要用 cin, cout

提示5:错的比较多的测试点特征为:①测试点 1 一开始只有一个数，然后不断执行操作 1,2,1,2,....，执行 10^5 次 ②测试点 2 一开始有 10^5 个数，删除 10^5-1 次，然后插入 1 次 ③除测试点 9 质量是常数外，其他测试点质量都是 [1,10^5] 内随机数

鉴于过题人数过少，现放出本题的数据生成器，链接 ，可用来生成数据对拍