There is a one-dimensional space of length $m$ and $n$ items, where the $i$-th item has length $a_i$. Items are placed into the space in order of their index from smallest to largest. For the $i$-th item:

• If there exists a contiguous empty space of length at least $a_i$ in the current space, you must place the $i$-th item into a contiguous empty space of length $a_i$.
• Otherwise, the $i$-th item cannot be placed, and you skip it.

You need to output all possible total occupied space lengths after considering all items in order of their index. The total occupied space length is defined as the sum of the lengths of all items that were successfully placed into the space.

Input

The first line contains two integers $m$ and $n$, representing the space length and the number of items, respectively. The second line contains $n$ integers $a_1, \dots, a_n$, representing the lengths of each item in order.

Output

Output two lines. The first line contains an integer $S$, representing the number of possible total occupied space lengths. The second line contains $S$ integers $b_1, \dots, b_S$, outputting all possible total occupied space lengths in increasing order. Note that you must ensure $b_1, \dots, b_S$ are distinct and complete.

Examples

Input 1

8 4
3 4 1 2

Output 1

4
4 6 7 8

Note 1

The figure below shows one possible way to achieve each of the occupied space lengths 4, 6, 7, and 8:

Figure 1: Example 1 explanation

Examples

Input 2

(See 2.in in the problem directory)

Output 2

(See 2.ans in the problem directory)

Subtasks

For all test data, $1 \le m, a_i \le 10^{16}$, $1 \le n \le 14$.