Equal sums (3) P11655

Statement

Write a program that, given a natural number $s$ and $n$ natural numbers $x_1, \dots, 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 a natural number $s$ , followed by a number $n > 0$ , followed by $x_1, \dots, x_n$ .

Output

Print all the subsets whose sum is $s$ that can be made up with $x_1, \dots, x_n$ .

Information about the checker

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

Hint

For this exercise, a very simple algorithm can be too slow.

Public test cases

Input

6
7
1 6 0 1 3 0 2

Output

{1,3,2}
{1,3,0,2}
{0,1,3,2}
{0,1,3,0,2}
{6}
{6,0}
{6,0}
{6,0,0}
{1,3,2}
{1,3,0,2}
{1,0,3,2}
{1,0,3,0,2}

Input

10
10
1 1 1 1 1 1 1 1 1 1

Output

{1,1,1,1,1,1,1,1,1,1}

Information

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