C0721 [BJWC2017]神秘物质

21ZZ 年，冬。

小诚退休以后， 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器，整天研究各种微观粒子。这一天， 小诚刚从研究所得到了一块奇异的陨石样本， 便迫不及待地开始观测。 在精密仪器的视野下，构成陨石的每个原子都无比清晰。 小诚发现， 这些原子排成若干列， 每一列的结构具有高度相似性。于是，他决定对单独一列原子进行测量和测试。被选中的这列共有 $N$ 个顺序排列的原子。 最初， 第 $i$ 个原子具有能量 $E_i$。 随着时间推移和人为测试， 这列原子在观测上会产生两种变化：

merge x e当前第 $x$ 个原子和第 $x+1$ 个原子合并，得到能量为 $e$ 的新原子；

insert x e在当前第 $x$ 个原子和第 $x+1$ 个原子之间插入一个能量为 $e$ 的新原子。

对于一列原子，小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值，称为区间极差。 因此， 除了观测变化外，小诚还要经常统计这列原子的两类数据：

max x y当前第 $x$ 到第 $y$ 个原子之间的任意子区间中区间极差的最大值；

min x y当前第 $x$ 到第 $y$ 个原子之间的任意子区间中区间极差的最小值。

其中，子区间指的是长度至少是 $2$ 的子区间。

小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？

样例输入 1

4 3
5 8 10 2
max 1 3
min 1 3
max 2 4

样例输出 1

5 2 8