Operator Signs

Interview

Time limit1sMemory limit1024 MB

Summary

Insert + or - between adjacent numbers so the left-to-right value equals the target, keeping every partial result within 10000, and print the lexicographically smallest expression.

Level: Medium6 of 10
Topics: Dynamic programming, Backtracking, Greedy, Implementation
Solved: No attempts yet

Problem

You are given a sequence of positive integers and a positive target value. Insert a plus (+) or minus (-) sign between each pair of adjacent numbers so that, evaluating the expression from left to right, its value equals the target. The first number has no sign in front of it.

Input

The first line contains the length of the sequence $N$ ( $1 \le N \le 1000$ ). The second line contains the members of the sequence separated by spaces. The third line contains the target value. Every member of the sequence and the target value are between $1$ and $10000$ inclusive.

Output

Print, on a single line, the expression formed by keeping the numbers in the given order and inserting + or - signs between them (the first number has no leading sign). Consider only expressions in which the absolute value of every partial result (evaluated left to right) never exceeds $10000$ ; at least one such expression is guaranteed to exist. Among all such expressions whose value equals the target, print the lexicographically smallest one (comparing the strings character by character, where + is considered smaller than -).

Examples5

Example 1
Input
```
5
5 4 3 2 1
5
```
Expected output
```
5+4-3-2+1
```
Example 2
Input
```
2
3 5
8
```
Expected output
```
3+5
```
Example 3
Input
```
2
5 3
2
```
Expected output
```
5-3
```
Example 4
Input
```
3
10 20 30
20
```
Expected output
```
10-20+30
```
Example 5
Input
```
4
1 1 1 1
2
```
Expected output
```
1+1+1-1
```