Petya 最近学习了名为“二叉堆”的数据结构。
他现在使用的堆允许执行以下操作:
- 将给定的数字放入堆中;
- 获取堆中最小元素的值;
- 从堆中提取最小元素;
因此,在任何时刻堆都包含多个整数(可能没有),其中一些可能是相等的。
为了更好地学习这个数据结构,Petya 拿了一个空堆并对其应用了上面的一些操作。此外,他还仔细地将所有操作及其结果记录到他的事件日志中,格式如下:
- insert x — 将值为 x 的元素放入堆中;
- getMin x — 堆中包含的最小元素的值等于 x;
- removeMin — 从堆中提取的最小元素(如果有多个实例,则仅提取一个实例)。
所有操作都是正确的,即每次应用 getMin 或 removeMin 操作时,堆中至少有一个元素。
当 Petya 外出吃午饭时,他的弟弟 Vova 来到房间,拿走了 Petya 日志中的一些页面并用它们制作纸船。
现在Vova担心他是否让Petya的操作顺序不一致。例如,如果按照事件日志中写入的顺序逐一应用操作,则 getMin 操作的结果可能与 Petya 记录的结果不同,并且某些 getMin 或 removeMin 操作可能不正确,因为应用时堆是空的。
现在Vova想要向事件日志中添加一些新的操作记录,以使结果操作顺序正确。也就是说,每次 getMin 操作的结果都等于记录中的结果,并且应用 getMin 和 removeMin 时堆非空。 Vova 希望尽快完成这件事,因为 Petya 随时可能回来。他要求你在当前日志中添加尽可能少的操作记录。请注意,可以在日志的开头、任意两个其他操作之间或日志的末尾添加任意数量的操作。
输入
输入的第一行包含唯一的整数 n (1 ≤ n ≤ 100 000) — Petya 日记中剩余的记录数。
以下 n 行中的每一行均按应用顺序描述当前日志中的记录。使用声明中描述的格式。输入中的所有数字均为绝对值不超过 109 的整数。
输出
输出的第一行应包含一个整数 m — 修改后的操作序列中可能的最小记录数。
接下来的 m 行应包含遵循输入格式(在语句中描述)的更正记录序列,每行一个并按照它们的应用顺序。输出中的所有数字均应为绝对值不超过 109 的整数。
请注意,操作的输入序列必须是输出序列的子序列。
保证存在包含不超过 1 000 000 次操作的正确答案。
示例
输入 #1
2 insert 3 getMin 4
输出 #1
4 insert 3 removeMin insert 4 getMin 4
输入 #2
4 insert 1 insert 1 removeMin getMin 2
输出 #2
6 insert 1 insert 1 removeMin removeMin insert 2 getMin 2
注意
在第一个样本中,将数字3插入堆后,最小数字为3。要使第一个getMin的结果等于4,应先从堆中删除数字3,然后将数字4添加到堆中。
在第二个示例案例中,编号 1 被插入两次,因此应类似地删除两次。