One-Dimensional Packing

Given a one‐dimensional space of length \(m\) and \(n\) items with lengths \(a_1, a_2, \dots, a_n\), the items are considered in increasing order of their indices. For the \(i\)-th item, if there exists a contiguous empty segment of length at least \(a_i\), you must place the item into a contiguous subsegment of length exactly \(a_i\) within one of those empty segments. Otherwise, the \(i\)-th item is skipped.

Your task is to determine all possible values for the space occupancy, defined as the sum of the lengths of the items that get placed after processing all items in order. Note that the occupancy is equal to \(m\) minus the total length of the remaining free space. Output all distinct possible occupancy values in increasing order.

inputFormat

The first line contains two integers \(m\) and \(n\), representing the length of the space and the number of items respectively. The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), where \(a_i\) denotes the length of the \(i\)-th item.

outputFormat

Output all distinct possible space occupancy values (i.e. the total length occupied by the placed items) in increasing order, separated by a space.

sample

5 2
2 3

2 5