정확한 산술

집합 $X$를 모든 유리수와, $q \sqrt{r}$ 꼴의 수 전체로 정의한다. 여기서 $q$는 $0$이 아닌 유리수이고 $r$은 $1$보다 큰 정수이며, $r$은 $1$ 외에 제곱수를 약수로 가지지 않는다. 또한 $X^{*}$를 $X$의 원소를 하나 이상 더한 합으로 나타낼 수 있는 수 전체의 집합으로 정의한다.

$X^{*}$의 값을 다루는 스택 기반 계산기 $Y$를 생각하자. $Y$가 가진 명령은 다음과 같다.

• push $n$: 피연산자로 주어진 정수를 스택에 넣는다.
• add: 스택 꼭대기에서 두 값 $x_1$과 $x_2$를 이 순서로 꺼내고, $(x_2 + x_1)$을 스택에 넣는다.
• sub: 스택 꼭대기에서 두 값 $x_1$과 $x_2$를 이 순서로 꺼내고, $(x_2 - x_1)$을 스택에 넣는다.
• mul: 스택 꼭대기에서 두 값 $x_1$과 $x_2$를 이 순서로 꺼내고, $(x_2 \cdot x_1)$을 스택에 넣는다.
• div: 스택 꼭대기에서 두 값 $x_1$과 $x_2$를 이 순서로 꺼내고, $(x_2 / x_1)$을 스택에 넣는다. 여기서 $x_1$은 $X^{*}$가 아니라 $X$에 속하는 $0$이 아닌 값이어야 한다.
• sqrt: 스택에서 값 $x$ 하나를 꺼내고, $x$의 제곱근을 스택에 넣는다. 여기서 $x$는 음이 아닌 유리수여야 한다.
• disp: 스택에서 값 $x$ 하나를 꺼내고, $x$의 문자열 표현을 디스플레이에 출력한다. 표현 규칙은 아래에 나온다.
• stop: 계산을 끝낸다. 이 명령을 호출할 때 스택은 비어 있어야 한다.

처음에 스택은 비어 있다. 모든 명령을 실행할 때 스택에는 충분한 수의 값이 있어야 한다. 또한 기계 $Y$의 한계로, 스택에 이미 $256$개의 값이 저장되어 있으면 더 이상 값을 넣을 수 없다. 스택에 넣는 값에도 여러 제약이 있다.

• 유리수는 기약분수로 나타냈을 때 분자와 분모의 절댓값이 $32\,768$을 넘지 않아야 한다.
• $X$의 원소를 $q \sqrt{r} = (a / b) \sqrt{r}$ 꼴로 나타냈을 때, $|a \sqrt{r}| \le 32\,768$이고 $|b| \le 32\,768$이어야 한다.

$X^{*}$의 원소는 합의 각 항이 위 조건을 만족해야 한다.

기계 $Y$에서 값의 문자열 표현 규칙은 다음과 같다.

• 유리수는 정수이거나 분모가 $1$보다 큰 기약분수로 나타낸다.
• 분수는 $\mathit{num}$/$\mathit{den}$으로 나타낸다. $\mathit{num}$은 분자이고 $\mathit{den}$은 분모이다. 음수 앞에는 부호 문자 -가 붙는다.
• $q \sqrt{r}$ 꼴의 수는 $|q| = 1$인 경우를 제외하고 $\mathit{rep}$*sqrt($r$)으로 나타낸다. $|q| = 1$인 경우에는 $q = 1$이면 sqrt($r$)로, $q = -1$이면 -sqrt($r$)로 나타낸다. 여기서 $\mathit{rep}$는 $q$의 문자열 표현이다.
• $X$의 원소 두 개 이상의 합은 $0$이 아닌 모든 원소의 문자열 표현을 이항 연산자 +로 이어 붙여 나타낸다. 이때 근호가 같은 항은 모두 하나로 합쳐지고, 항은 근호 성분이 커지는 순서로 나열한다. 이 규칙에서 모든 유리수는 $\sqrt{1}$을 동반하는 것으로 본다. 이항 연산자 + 앞뒤에는 공백 문자가 정확히 하나씩 있고, 다른 위치에는 공백 문자가 없다.

다음은 올바른 문자열 표현의 예이다.

0
1
-1/10
2*sqrt(2) + 1/2*sqrt(3) + -1/2*sqrt(5)
1/2 + sqrt(10) + -sqrt(30)

여러분의 과제는 기계 $Y$를 시뮬레이션하는 프로그램을 작성하는 것이다.

입력은 $3000$개 이하의 명령으로 이루어진다. 각 줄에는 명령이 하나씩 있다. 모든 명령은 올바른 방식으로 호출된다고 가정한다. 명령 "stop"은 전체 입력의 마지막에 한 번만 나타난다.

기계 $Y$가 디스플레이에 출력하는 문자열을 출력한다. 각 문자열은 한 줄에 하나씩 출력한다.