Write a program that, given an integer number s
and n integer numbers x_{1}, …, x_{n},
prints all the subsets
(maybe with repeated numbers, but using every x_{i} at most once)
whose sum is exactly s.

Input

Input consists of an integer number s,
followed by a number n > 0,
followed by x_{1}, …, x_{n}.

Output

Print all the subsets whose sum is s
that can be made up with x_{1}, …, x_{n}.

You can print in any order both the solutions and the elements inside each solution.

Hint

For this exercise, simple backtracking solutions are accepted. No optimizations are required.

Public test cases

**Input**

6 7 1 -2 0 3 -4 5 1

**Output**

{5,1} {0,5,1} {-2,3,5} {-2,0,3,5} {1,5} {1,3,-4,5,1} {1,0,5} {1,0,3,-4,5,1}

**Input**

0 2 -5 5

**Output**

{} {-5,5}

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Codon Python
- User solutions
- C++ Python