思路概述

把内存看作长度为 n 的数组，堆指针 hp 表示下一个要写入的堆位置（从 0 向右生长），栈指针 sp 表示下一个要写入的栈位置（从 n-1 向左生长）：

• 初始：hp = 0，sp = n-1，内存为给定初值。
• 入堆（opt=0，给定 x）：若 hp > sp ⇒ 无可用空间，Memory allocation failure；否则写 a[hp]=x，hp++。
• 出堆（opt=1）：若 hp == 0 ⇒ 堆空，Invalid heap address；否则 hp--（不清空内存）。
• 入栈（opt=2，给定 x）：若 hp > sp ⇒ 无可用空间，Memory allocation failure；否则写 a[sp]=x，sp--。
• 出栈（opt=3）：若 sp == n-1 ⇒ 栈空，Invalid stack address；否则 sp++（不清空内存）。

题目内容

众所周知，计算机内存中有堆和栈，堆从低地址向高地址生长，栈从高地址向低地址生长，如下图所示:

小A的电脑的内存可以视作一个一维数组，地址从 $0$ 到 $n-1$ 编号，最开始堆指针指向 $0$ 号位置，栈指针指向 $n-1$ 号位置，接下来小A 将进行 $m$ 次操作，以如下形式给出：

• $0 \ x$：将一个值为 $x$ 的数放入堆

• $1$：将堆顶元素弹出

• $2 \ x$：将一个值为x的数放入栈

• $3$：将栈顶元素弹出

要保证计算机正常运行，则当元素入堆时，需要判断内存是否有剩，即存放的位置既不能超出内存范围，也不能更覆盖栈中的内容。当元素出堆时，需要判断堆中是否还有元素，同时只移动堆指针而不需将原堆顶存储的值清空。元素入栈出栈的情况也类似，入栈时要求内存有剩，出栈时要求栈不为空且不覆盖原本栈顶内存。如果不满足条件，那么小A的电脑将立即崩溃！

现在给出内存中的原始内容及小A 进行的 $m$ 次操作，小$A$想要知道，他的这些操作是否会使电脑崩溃?若在元素出堆时系统崩溃，则输出 "$invalid$ $heap$ $address$”(不包括引号，后同)；若在元表出栈时系统崩溃，则输出 "$invalid$ $stack$ $address$” ；若元素入堆或入栈时系统崩溃，则输出"$Memory$ $allocation$ $faiure$ ” ；若所有操作都没有导致系统崩溃则输出“ $Done$ "。同时小 A 还希望得到系统崩溃前一瞬间或所有操作正常结束后内存中的内容；以方便他恢复工作进度或进行下一步工作。

输入描述

第一行两个正整数 $n,m(1≤n,m≤400)$ ，表示内存空间的大小和操作次数。

第二行 $n$ 个 $32$ 位无符号整数 $a_i$ ，表示内存第 $i$ 个位置初始存放的值。

接下来 $m$ 行，每行先读入 “$0,1,2,3$” 中的一个整数 $opt$ ，表示操作种类，当 $opt$ 为偶数时再读入一个 $32$ 位无符号整数 $x$ ，表示入堆或入栈的元素。

输出描述

第一行输出一个字符串，表示系统崩溃原因或正常完成所有操作。

第二行 $n$ 个整数，表示系统崩溃前或正常完成操作后的内存内容。

样例1

输入

3 5
1 2 3
2 4
0 5
1
1
0 6

输出

Invalid heap address
5 2 4

说明

样例解释第一次操作将 $4$ 入栈，此时内存为 {$1,2,4$}，堆大小为 $0$ ，栈大小为 $1$ 。

第二次操作将 $5$ 入堆，此时内存为 {$5,2,4$}，堆大小为 $1$ ，栈大小为 $1$ 。

第三次操作出堆，此时内存为 {$5,2,4$}，堆大小为 $0$ ，栈大小为 $1$ 。

第四次操作出堆，但堆为空，因此系统崩溃，输出错误信息并将操作前内存输出，程序结束。