有一天,格里沙和戴安娜这两个学生发现自己来到了大学化学实验室。在实验室里,学生们找到了n支装有汞的试管,编号从1到n,并决定进行一个实验。
该实验由 q 个步骤组成。在每个步骤中,都会发生以下操作之一:
1. Diana 倒出 pi 号试管中的所有内容物,然后倒出恰好 xi 升水银。
2. 让我们考虑一下向管子中添加 vi 升水的所有方法;对于每种方式,让我们计算管中液体(水和汞)的体积,其中水具有最大液体量;最后让我们找到计数的最大值中的最小值。这就是学生想要数的数字。此时,学生们实际上并没有倒水银。他们在不改变试管内容物的情况下进行计算。
不幸的是,计算结果太复杂了,学生们请求你帮助他们。帮助他们进行所描述的实验。
输入
第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 105) — 管数和实验步骤数。下一行包含 n 个空格分隔的整数:h1, h2, ..., hn (0 ≤ hi ≤ 109),其中 hi 是实验开始时第 i 管中汞的体积。
接下来的 q 行包含以下格式的游戏动作:
- 形式为“1 pi xi”的行表示第一种类型的动作 (1 ≤ pi ≤ n; 0 ≤ xi ≤ 109)。
- 形式“2 vi”的行表示第二类型的动作(1 ≤ vi ≤ 1015)。
保证至少有一个第二类型的动作。保证描述实验的所有数字都是整数。
输出
对于第二种类型的每个操作,打印计算值。如果答案的相对误差或绝对误差不超过 10 - 4,则认为答案是正确的。
示例
输入 #1
3 3 1 2 0 2 2 1 2 1 2 3
输出 #1
1.50000 1.66667
输入 #2
4 5 1 3 0 1 2 3 2 1 1 3 2 2 3 2 4
输出 #2
1.66667 1.00000 2.33333 2.66667