分考场

题目描述

古语有云：春风得意马蹄疾，一日看尽长安花。

当然在一场考试中所有人都春风得意马蹄疾是不可能的，尤其是碰到一些毒瘤出题人的时候。

又到了每月一次的月考，又是 xf 老师出题。

上一次 xf 老师出的题太毒瘤了，平均分只有 40 4040 多，同学们都非常不满意，毕竟别的科的平均分都是 80 8080 多。

这次 xf 为了不被同学们寄刀片，想了一个办法：只公布所有考场的平均分的平均分。这样他就可以通过调整考场的分配方式，使得平均分显得高。（每个考场都可以容纳无限人）

每次考试也不是所有同学都参加的，只有学号在 [ l , r ] [l,r][l,r] 这个区间中的同学会参加。

他想知道对于每次考试，他调整过考场后，所有考场的平均分的平均分的最大值。

当然，同学们也可能会努力学习或整日颓废使成绩发生改变。

输入格式

输入的第一行包含一个整数 n nn。

第二行包含 n nn 个整数，第 i ii 个数 v i v_{i}v 

i ，表示开始时每个同学的成绩。

第三行包含一个整数 q qq，表示有 q qq 次操作。

之后 q qq 行，每行描述一个操作，第一个数表示操作类型。

如果操作为 1 p x 1 p x1px，表示学号为 p pp 的同学分数变为 x xx。

如果操作为 2 l r k 2 l r k2lrk, 表示把学号在 [ l , r ] [l,r][l,r] 中的同学分成 k kk 个考场，求这 k kk 个考场的平均分的平均分的最大值。

输出格式

对于每个 2 操作输出一行，四舍五入保留正好 3 位小数。

测试样例1

Input：

5

5 3 4 2 1

5

2 1 4 3

1 4 8

2 3 5 3

1 2 2

2 1 3 2

Output：

3.833

4.333

4.000

Explanation：

第一个操作询问学号在 [1, 4] 之间的同学分成 3 个考场的平均分的平均分的最大值，最优策略是：{1}, {2, 4}, {3}，平均分是 ${formula_1}

第二个操作把学号为 4 的同学的分数变为 8。

第三个操作询问学号在 [3, 5] 之间的同学分成 3 个考场的平均分的平均分的最大值，最优策略是：{3}, {4}, {5}。

第四个操作把学号为 2 的同学分数变为 2。

第五个操作询问学号在 [1, 3] 之间的同学分成 2 个考场的平均分的平均分的最大值，最优策略是：{1}, {2 3}。