Dessert

Interview

Time limit1sMemory limit1024 MB

Summary

Insert +, -, or . between cows numbered 1 to N so the expression evaluates to 0, then list the first 20 expressions and count all of them.

Level: Medium4 of 10
Topics: Backtracking, Brute force, Implementation
Solved: No attempts yet

Problem

FJ has a new rule for the cows lining up for dinner. The N (3 ≤ N ≤ 15) cows must line up in order, and they must place a napkin between each pair of adjacent cows. Each napkin has a "+", "-", or "." on it. To earn their dessert, the cow numbers and napkins must form a numerical expression that evaluates to 0. The "." napkin lets the cows build bigger numbers. Consider this equation for seven cows:

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

This means 1-23-45+67, which evaluates to 0. Your job is to help the cows get dessert. (Note: "... 10 . 11 ..." uses the number 1011 in its calculation.)

Input

One line with a single integer, N.

Output

Print one line for each of the first 20 possible expressions, then a line with a single integer that is the total number of possible answers. Each expression line has the form number, space, napkin, space, number, space, napkin, and so on. The output is in lexicographic order, with "+" before "-" and "-" before ".". If fewer than 20 expressions can be formed, print all of them.

Examples1

Example 1

Input

Expected output

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
6