Description

Consider an increasing sequence of numbers from $1$ to $N$: $1, 2, 3, \ldots, N$.

Insert + for addition, - for subtraction, or (a space) for blank between each pair of consecutive numbers (for example, 1-2 3 equals 1-23). Do not insert any symbol before the first number.

Evaluate the resulting expression and determine whether its value is $0$. Write a program to find all expressions of length $N$ whose value is zero.

Input Format

A single line containing an integer $N$ ($3 \leq N \leq 9$).

Output Format

In ASCII order, output all expressions obtained by inserting +, -, or (space) between each pair of consecutive numbers such that the resulting expression evaluates to $0$. Print one expression per line.

7

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

Hint

Translated from NOCOW.

USACO 2.3.

Translated by ChatGPT 5