Holy cow, Vim! (Hard)

어린 Johnny는 여름 프로그래밍 캠프에 다니고 있다. 첫 과제는 정수 x를 읽어 같은 수 x를 출력하는 프로그램을 작성하는 것이었다. Johnny의 프로그램은 이미 잘 동작하고 있었는데, 사고가 벌어졌다. Vim 편집기를 쓰다가 Johnny가 정신없이 아무 키나 눌렀고, 프로그램이 거꾸로 뒤집혔다. 즉, 프로그램의 줄 순서가 뒤바뀌어 버린 것이다.

놀랍게도 프로그램은 여전히 동작했지만, 이제는 다른 일을 했다. x를 읽고 x2를 출력한 것이다.

Johnny는 줄을 다시 올바른 순서로 되돌리려고 자기가 뭘 눌렀는지 기억해 보다가 또 실수해서, Vim이 프로그램의 줄을 정렬해 버렸다. 새 프로그램을 실행해 본 Johnny는 말문이 막혔다. 이제 프로그램은 x를 읽고 −x를 출력했다.

"Holy cow, Vim은 마법이야! 평생 Vim만 쓸 거야!"라고 Johnny가 외쳤다.

"그건 아무도 Vim을 종료하는 법을 몰라서 그런 거야"라고 다른 학생이 받아쳤다.

Johnny의 프로그램과 똑같이 동작하는 프로그램을 작성할 수 있는가?

이 문제에서는 간단한 스택 기반 프로그래밍 언어를 사용한다. 메모리는 부호 있는 정수의 스택이다. 여러 명령이 스택에 값을 넣거나 스택 맨 위에서 값을 꺼낸다. 스택은 처음에는 비어 있고, 프로그램이 끝날 때 비어 있지 않아도 된다.

프로그램은 여러 개의 줄로 이루어지고, 각 줄은 세미콜론으로 구분된 하나 이상의 명령으로 이루어진다. 명령은 다음 중 하나다.

• "input": 입력에서 정수 x를 읽어 스택에 넣는다. 프로그램 실행 중 "input"은 한 번만 실행할 수 있다.

• "jump j": 즉시 j번째 줄의 처음으로 점프한다. 줄은 0부터 n − 1까지 번호가 매겨지며, n은 줄의 개수다. j = n으로 점프하면 프로그램이 종료된다. j < 0 또는 j > n으로 점프하면 오류다.

• "pop": 스택에서 맨 위 원소를 제거한다. 스택이 비어 있으면 오류다.

• "print": 스택에서 맨 위 원소를 제거하고 그 값을 출력한다. 스택이 비어 있으면 오류다. 프로그램 실행 중 "print"는 한 번만 실행할 수 있다.

• "push p": 상수 p를 스택 맨 위에 넣는다.

• "dup": 스택 맨 위 원소를 복제한다. 현재 맨 위 원소가 t라면 "dup"은 "push t"와 같은 일을 한다. 스택이 비어 있으면 오류다.

• "+", "-", "*", "/": 스택에서 맨 위 원소 a를 꺼내고, 그다음 원소 b를 꺼내고, 각각 a + b, a − b, a ⋅ b, a/b를 0 방향으로 반올림한 값을 스택에 넣는다. 스택에 수가 두 개 미만이면 오류다. 0으로 나누는 것도 오류다.

이 언어는 매우 엄격하다. 여분의 공백이나 세미콜론 같은 것은 쓸 수 없다.

−231부터 231 − 1까지(포함)의 정수만 지원한다. 이 범위를 벗어나는 정수를 스택에 넣으면 오류다.

입력이 없다.

정수 x를 읽어 x를 출력하는 프로그램을 작성해야 한다. 단, 프로그램의 줄 순서를 뒤집으면(즉, 마지막 줄이 첫 줄이 되는 식으로) 새 프로그램이 x2를 출력해야 한다. 그리고 프로그램의 줄을 사전순으로 정렬하면 −x를 출력해야 한다.

|x|≤30 000이라고 가정할 수 있다.

프로그램은 최대 1000개의 줄을 가질 수 있다. 모든 유효한 x에 대해 프로그램은 최대 10 000개의 명령을 실행한 뒤 종료해야 한다.

각 줄은 최대 두 개의 명령을 포함할 수 있다.

위 프로그램은 x를 읽어 x − 7을 출력한다.

위 프로그램의 줄 순서를 뒤집으면 "print"가 첫 번째 명령이 되고, 빈 스택의 맨 위를 출력하려 하므로 프로그램이 실패한다.