solution

Để sinh mã cho các cấu trúc điều khiển (if, while, ...), trình biên dịch cần thêm các lệnh nhảy (jump) vào máy ảo ngăn xếp. Cho một máy ảo với ngăn xếp, một mảng bộ nhớ gồm $m$ ô (đánh số $0..m-1$, khởi tạo $0$), và một chương trình gồm $n$ lệnh được đánh số từ $0$ đến $n-1$ (con trỏ lệnh — program counter — bắt đầu tại $0$). Các lệnh gồm:

• PUSH x: đẩy hằng số $x$.
• LOAD i / STORE i: đọc/ghi ô nhớ $i$ (như đẩy/pop đỉnh ngăn xếp).
• DUP: nhân đôi phần tử ở đỉnh ngăn xếp (đẩy thêm một bản sao).
• ADD, SUB, MUL, DIV: pop $b$ (đỉnh), $a$ (kế đỉnh), đẩy lại $a \ \text{op} \ b$ (DIV lấy phần nguyên hướng về 0).
• JZ t: pop đỉnh ngăn xếp; nếu giá trị pop ra bằng $0$ thì con trỏ lệnh nhảy đến chỉ số $t$, ngược lại con trỏ lệnh tăng lên 1 như bình thường.
• JMP t: con trỏ lệnh nhảy đến chỉ số $t$ vô điều kiện.
• HALT: dừng chương trình ngay lập tức.

Sau mỗi lệnh không phải là lệnh nhảy, con trỏ lệnh tăng thêm 1. Chương trình cũng dừng khi con trỏ lệnh đi ra ngoài đoạn $[0, n-1]$ (kể cả khi nhảy đến đúng vị trí $t=n$, coi như kết thúc bình thường). Vì chương trình đầu vào có thể chứa vòng lặp không bao giờ dừng, hãy giới hạn số lệnh được thực thi tối đa là $2\,000\,000$ lệnh; nếu vượt quá giới hạn này, in ra TIMEOUT và dừng ngay (không in gì khác).

Nếu chương trình dừng bình thường (không vượt giới hạn), hãy in ra toàn bộ nội dung ngăn xếp cuối cùng, theo thứ tự từ đáy lên đỉnh (có thể rỗng).

Ví dụ: chương trình dưới đây tính tổng $1+2+\cdots+5$ bằng vòng lặp, dùng ô nhớ 0 làm biến đếm và ô nhớ 1 làm tổng tích lũy:

0: PUSH 5      6: LOAD 1      12: SUB
1: STORE 0     7: LOAD 0      13: STORE 0
2: PUSH 0      8: ADD         14: JMP 4
3: STORE 1     9: STORE 1
4: LOAD 0      10: LOAD 0
5: JZ 15       11: PUSH 1

Sau khi thực thi, vòng lặp dừng khi ô nhớ 0 (bộ đếm) về $0$, ô nhớ 1 chứa tổng $15$, ngăn xếp cuối cùng rỗng — chương trình in ra một dòng trống.