Ровно год назад на Пятой Липецкой командной олимпиаде школьников по программированию участникам была предложена задача, в которой нужно было вычислить сумму элементов массива, используя довольно необычный язык программирования и вычислительную машину. Вы можете вспомнить условие той самой задачи ниже.

Не так давно вы устроились на работу в известную компанию CodeHorses, которая занимается проведением соревнований по программированию. Вы подумали, что будет замечательно, если у участников появится возможность решать задачи по программированию при помощи стековой машины! Поэтому вы немедленно приступили к работе по созданию компилятора языка программирования для данной вычислительной машины.

Вам будет дана программа, написанная на языке стековой машины, исходное состояние стека и ограничение на максимальное время выполнения программы в тактах. От вас требуется определить корректность данной программы и состояние стека после окончания работы программы.

Формально, возможны четыре варианта развития событий:

1. Программа является синтаксически некорректной. В данном случае результатом считается Compilation error.
2. Программа является синтаксически корректной, однако завершается с ошибкой (например, POP из пустого стека). В этом случае результатом считается Runtime error.
3. Программа является синтаксически корректной, однако не успевает завершиться за указанное количество тактов. В этом случае результатом считается Time limit exceeded.
4. Программа является синтаксически корректной и завершается без ошибок не более, чем за указанное количество тактов. В этом случае результатом считается Accepted. В данном случае необходимо помимо вердикта вывести конечное состояние стека.

Ниже приведены выдержки из задачи прошлого года, описывающие машину, а также допустимые операции и их синтаксис. Если вы хорошо помните задачу, можете продолжать чтение с раздела «Входные данные».

У вас есть машина, память которой — это стек, элементы которого являются целыми числами. Количество элементов стека в данный момент мы будем обозначать как $$$sz$$$.

Напомним, что стек — это абстрактная структура данных, хранящая коллекцию элементов, и работающая по принципу LIFO (последним пришёл — первым вышел). Стек поддерживает две базовые операции: положить элемент на вершину стека, взять элемент с вершины стека. В качестве аналогии можно представить стопку тарелок: вы не можете оперировать с тарелками не на вершине стопки.

Список доступных инструкций приведен ниже. RTE (Runtime Error) обозначает, что выполнение программы завершилось с ошибкой.

• PUSHZ — положить на стек 0;
• POP — взять со стека $$$x$$$ (если $$$sz \lt 1$$$, то RTE);
• SWAP2 — взять со стека $$$x$$$, взять со стека $$$y$$$, положить на стек $$$x$$$, положить на стек $$$y$$$ (если $$$sz \lt 2$$$, то RTE);
• SWAP3 — взять со стека $$$x$$$, взять со стека $$$y$$$, взять со стека $$$z$$$, положить на стек $$$y$$$, положить на стек $$$x$$$, положить на стек $$$z$$$ (если $$$sz \lt 3$$$, то RTE);
• COPY — взять со стека $$$x$$$, положить на стек $$$x$$$, положить на стек $$$x$$$ (если $$$sz \lt 1$$$, то RTE);
• INC — взять со стека $$$x$$$, положить на стек $$$x+1$$$ (если $$$sz \lt 1$$$, то RTE);
• DEC — взять со стека $$$x$$$, положить на стек $$$x-1$$$ (если $$$sz \lt 1$$$, то RTE);
• ADD — взять со стека $$$x$$$, взять со стека $$$y$$$, положить на стек $$$x+y$$$ (если $$$sz \lt 2$$$, то RTE);
• SUB — взять со стека $$$x$$$, взять со стека $$$y$$$, положить на стек $$$x-y$$$ (если $$$sz \lt 2$$$, то RTE);

Также доступны условный оператор и цикл while. Чтобы их использовать, сначала нужно научиться задавать какие-то условия:

• EZ — TRUE если на вершине стека 0 (если $$$sz \lt 1$$$, то RTE);
• GZ — TRUE если на вершине стека положительное число (если $$$sz \lt 1$$$, то RTE);
• HAVE1, HAVE2 — TRUE если $$$sz \ge k$$$ (обратите внимание, что $$$k \in \{ 1, 2 \}$$$, HAVE3 не является условием)

Условный оператор:

IF cond THEN
BEGIN
    body
END

Цикл while:

WHILE cond DO
BEGIN
    body
END

В обоих случаях cond — одно из условий, описанных выше, body — тело условного оператора или цикла — последовательность команд, которые будут выполнены, если cond=TRUE (один раз в случае условного оператора, или много раз в случае цикла). Циклы и условные операторы могут быть вложенными.

Любой пробел и перевод строки может быть заменён на любое ненулевое количество пробелов и переводов строки, вставлять пробелы и переводы строки внутрь инструкций нельзя.

Каждая инструкция (а также проверки условия для условного оператора и цикла) выполняется 1 такт.

Верхний регистр в названиях инструкций важен.