Stacking Up

Time limit1sMemory limit1024 MB

Summary

Given a target stack of positive integers, output a program using only 1, d, and + that builds it from an empty stack, where + also decrements the remaining entries.

Level: Medium6 of 10
Topics: Math, Implementation, Recursion
Solved: No attempts yet

Problem

Stacy has recently started work at Stacks“R”Us, a leading manufacturer of stack-related products such as children's blocks, pancake spatulas, and dining hall tray dispensers. As a new employee, she has been assigned to test the latest model in the company's line of automated electronic stack machines, the Stackulator 3000.

The Stackulator 3000 holds a single stack of positive integers in its memory and supports three instructions: 1, d, and +. The first two are fairly standard:

1: push the number 1 onto the top of the stack.
d: duplicate the number on top of the stack, that is, take the number on top and push another copy of it. It is an error to execute d on an empty stack.

The + instruction did not come out as designed. Miscommunication between the designer and the hardware team, along with confusion between a stack pointer and a stack entry, caused it to decrement every remaining entry:

+: pop the top two numbers, decrement all remaining stack entries by one, then push the sum of the two popped numbers. It is an error to execute + on a stack with fewer than two integers.

For example, executing the program 1d+11+ produces the stack states shown in Figure J.1, ending with a stack of two entries, $1$ on the bottom and $2$ on the top.

Figure J.1: Execution of 1d+11+

If a stack entry of $1$ is decremented during an addition, it is removed from the stack, since the stack can only hold positive integers.

Stan proposed splitting the work evenly. Stan comes up with stacks, and Stacy writes Stackulator 3000 programs that generate them. Help Stacy by writing programs that generate the stacks Stan provides.

Input

The first line contains an integer $n$ with $1 \le n \le 1\,000$ . The next line contains $n$ space-separated positive integers, the desired contents of the stack from bottom to top. Each integer $x$ satisfies $1 \le x \le 10^6$ .

Output

Output a single line containing a valid Stackulator 3000 program that, when run on an empty stack, leaves the desired stack. The program may use only the characters 1, d, and +, and it may be at most $100\,000$ characters long. If several programs work, output any of them.

Examples2

Example 1
Input
```
3
1 1 1
```
Expected output
```
1dd
```
Example 2
Input
```
3
1 2 3
```
Expected output
```
11+1+1+1+1+11+1+1+11+1+
```