Game Show Math

Time limit2sMemory limit128 MB

Summary

Insert +, -, *, / between the given numbers in order, left to right, so the running value hits the target; output the smallest expression or NO EXPRESSION.

Level: Medium6 of 10
Topics: DFS, Backtracking, Implementation
Solved: No attempts yet

Problem

A television game show has a segment that gives a contestant a sequence of positive integers and one target integer. The contestant must build a single arithmetic expression that uses every number in the sequence exactly once, joined by the operators +, -, *, and /. Each operator may be used any number of times, including zero.

The expression is evaluated strictly from left to right, ignoring the usual order of operations, and its result must equal the target.

The expression must obey three rules:

The numbers must appear in the same order as in the input.
Division / may be used only when it is exact (the running result divides evenly, with no remainder).
After every operator is applied, the running result must be an integer in the range $-32000$ to $32000$ , inclusive.

Input

The first line contains the number of test cases $n$ .

Each of the next $n$ lines describes one test case. The line starts with the count of numbers $p$ ( $0 < p \le 100$ ), followed by the $p$ positive integers of the sequence, followed by the target integer. The sequence may contain duplicate numbers.

Output

For each test case, print one line.

If at least one valid expression reaches the target, print that expression followed by = and the target, with no spaces (for example 5+7/4=3). The expression must contain all $p$ numbers and the $p-1$ operators. Because several expressions may reach the same target, print the lexicographically smallest such expression (the smallest when the whole line is compared character by character as text).

If no valid expression exists, print NO EXPRESSION.

Examples5

Example 1

Input

3
3 5 7 4 3
2 1 1 2000
5 12 2 5 1 2 4

Expected output

5+7/4=3
NO EXPRESSION
12+2-5-1/2=4

Example 2
Input
```
1
1 42 42
```
Expected output
```
42=42
```
Example 3
Input
```
1
1 100 99
```
Expected output
```
NO EXPRESSION
```
Example 4
Input
```
1
2 2 3 6
```
Expected output
```
2*3=6
```
Example 5
Input
```
1
2 8 5 3
```
Expected output
```
8-5=3
```