스택 쌓기

Stacy는 최근 Stacks“R”Us에 입사했다. 이 회사는 어린이용 블록, 팬케이크 뒤집개, 구내식당 쟁반 디스펜서 등 스택 관련 제품을 만드는 대형 제조사다. 신입인 Stacy는 회사의 자동 전자 스택 기계 라인업 최신 제품인 Stackulator 3000을 테스트하는 일을 맡았다.

Stackulator 3000은 양의 정수로 이루어진 스택 하나를 메모리에 보관하며, 1, d, + 세 가지 명령어를 지원한다. 앞의 두 명령어는 평범하다.

• 1: 숫자 1을 스택 맨 위에 넣는다.
• d: 스택 맨 위의 숫자를 복제해서 한 개 더 맨 위에 넣는다. 빈 스택에서 d를 실행하면 오류다.

+ 명령어는 설계대로 동작하지 않는다. 설계자와 하드웨어 팀 사이의 소통 문제와 스택 포인터와 스택 원소를 혼동한 탓에, 남은 원소가 모두 1씩 줄어든다.

• +: 맨 위의 두 숫자를 꺼내고, 남은 모든 원소를 1씩 줄인 뒤, 꺼낸 두 숫자의 합을 스택에 넣는다. 원소가 두 개 미만인 스택에서 +를 실행하면 오류다.

예로 프로그램 1d+11+을 실행하면 그림 J.1과 같이 스택 상태가 바뀌고, 최종적으로 아래가 $1$, 위가 $2$인 두 원소 스택이 남는다.

그림 J.1: 1d+11+의 실행

덧셈 중에 값 $1$인 원소가 1 줄어들면, 스택에는 양의 정수만 들어갈 수 있으므로 그 원소는 스택에서 제거된다.

Stan은 작업을 나누자고 제안했다. Stan이 스택을 만들면 Stacy가 그 스택을 만들어내는 Stackulator 3000 프로그램을 작성한다. Stan이 준 스택을 생성하는 프로그램을 작성해 Stacy를 도와라.

첫 줄에 정수 $n$이 주어진다. 범위는 $1 \le n \le 1\,000$이다. 다음 줄에는 공백으로 구분된 양의 정수 $n$개가 주어지며, 이는 아래에서 위 순서로 원하는 스택의 내용이다. 각 정수 $x$는 $1 \le x \le 10^6$을 만족한다.

빈 스택에서 실행했을 때 원하는 스택을 만드는 올바른 Stackulator 3000 프로그램을 한 줄로 출력한다. 프로그램은 1, d, + 문자만 사용할 수 있고, 길이는 $100\,000$자를 넘을 수 없다. 조건을 만족하는 프로그램이 여럿이면 그중 아무것이나 출력해도 된다.