Barbells

Your local gym has $n$ barbells and $m$ plates. In order to prepare a weight for lifting, you must choose a single barbell, which has two sides. You then load each side with a (possibly empty) set of plates. For safety reasons, the plates on each side must sum to the same weight. What weights are available for lifting?

Input

The first line contains the integers $n$ and $m(1\le n,m\le 14)$.

The second line contains $n$ integers $b_1,...,b_n(1\le b_i\le 10^8)$, denoting the weights of the barbells in grams.

The third line contains $m$ integers $p_1,...,p_m(1\le p_i\le 10^8)$, denoting the weights of the plates in grams.

Output

Print a sorted list of all possible distinct weights in grams, one per line.

Examples

For example, suppose that there are two barbells weighing $100$ and $110$ grams, and five plates weighting $1,4,5,5$ and $6$ grams, respectively. Then, there are six possible weights available for lifting.