H. 圣母的眼泪
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

末日之战的场面犹如太空上的赤壁之战、火烧连营。人类联合舰队像一条绑成一串的蚂蚱，被水滴整整的一列洞穿。炸到第三列时，傲慢的人类战舰终于意识到要逃跑，可水滴以一种超出人类理解的锐角转弯迅速拦截，像一枚死神的绣花针。

水滴除了一列一列穿透每一艘战舰的核聚变燃料舱外 ，还能够通过在每一列战舰的 薄弱点 释放特殊电磁波来瘫痪一整列人类联合舰队。舰队共有 $$$n$$$ 艘 ，可以假设其所处位置都在一根数轴上 ，第 $$$i$$$ 艘战舰的位置为 $$$X_i$$$ 。 薄弱点 被定义为数轴上到这一列战舰的距离之和最小的点构成的区间的中点。

但是人类联合舰队的垂死挣扎会让薄弱点位置更改 ，请在每次人类舰队的行为发生后计算薄弱点的位置。舰队共有三种行为：

行为 $$$1$$$ ：一艘新战舰加入到这一列的 $$$K$$$ 位置。

行为 $$$2$$$ ：所有战舰向右移动 $$$K$$$ 个单位。

行为 $$$3$$$ ：所有战舰位移到关于 $$$x=K$$$ 对称的位置。

Input

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ （ $$$1 \le n , m \le 2 \cdot 10^5$$$ ） ， 分别表示初始战舰个数与行为个数 。

第二行包含 $$$n$$$ 个整数 $$$X_1, X_2, \dots, X_n$$$ （ $$$-10^6 \le X_i \le 10^6$$$ ） ， 表示每艘战舰的初始位置 。

接下来 $$$m$$$ 行 ， 每行包含两个整数 $$$op$$$ 和 $$$K$$$ （ $$$1 \le op \le 3$$$ ， $$$-10^6 \le K \le 10^6$$$ ） ， 分别表示行为编号和行为内容：

若 $$$op = 1$$$ ， 表示一艘新战舰加入到 $$$K$$$ 位置 。

若 $$$op = 2$$$ ， 表示所有战舰向右移动 $$$K$$$ 个单位 。

若 $$$op = 3$$$ ， 表示所有战舰移动到关于 $$$x=K$$$ 对称的位置 。

所有行为都按照时间顺序给出 ， 且同一位置可能存在多艘战舰 。

Output

共输出 $$$m+1$$$ 行。

第一行输出人类舰队所有行为发生前的薄弱点位置。

接下来的 $$$m$$$ 行 ，对于每次行为产生后 ，输出当前舰队的薄弱点位置。

选手输出的答案与标准答案的绝对误差或相对误差不超过 $$$10^{-4}$$$ 即被视为正确。

Example
Input
3 4
4 2 1
1 3
1 5
2 1
3 5
Output
2.0000000000
2.5000000000
3.0000000000
4.0000000000
6.0000000000
Note

初始时 ，战舰的位置为 $$$1, 2, 4$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[2, 2]$$$ ，该区间的中点为 $$$2.0$$$ 。

第一次行为后 ，新增一艘位于 $$$3$$$ 的战舰 ，所有战舰位置为 $$$1, 2, 3, 4$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[2, 3]$$$ ，该区间的中点为 $$$2.5$$$ 。

第二次行为后 ，新增一艘位于 $$$5$$$ 的战舰 ，所有战舰位置为 $$$1, 2, 3, 4, 5$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[3, 3]$$$ ，该区间的中点为 $$$3.0$$$ 。

第三次行为后 ，所有战舰向右移动 $$$1$$$ 个单位 ，所有战舰位置变为 $$$2, 3, 4, 5, 6$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[4, 4]$$$ ，该区间的中点为 $$$4.0$$$ 。

第四次行为后 ，所有战舰关于 $$$x=5$$$ 对称 ，所有战舰位置变为 $$$4, 5, 6, 7, 8$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[6, 6]$$$ ，该区间的中点为 $$$6.0$$$ 。