Barbells

Time limit2sMemory limit512 MB

Summary

Given up to 14 bars and 14 plates, find every total weight obtainable by putting plates on both sides of one bar so that the two sides balance.

Level: Medium6 of 10
Topics: Brute force, Hash map, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

The gym down the street has $b$ bars and $p$ plates. To prepare a weight for lifting you pick one bar and load plates onto its two sides. The set of plates on a side may be empty. For safety the two sides must balance: their plate weights have to sum to the same value. The plates on one side may differ from the plates on the other side, as long as the two sums are equal.

Each plate can be used at most once, and any plate may be left unused. The lifting weight is the weight of the bar plus the weight of all plates loaded on both sides. Find every weight that is available for lifting.

Input

The first line contains two integers $b$ and $p$ ( $1 \le b, p \le 14$ ), the number of bars and the number of plates. Each of the next $b$ lines contains one integer $x$ ( $1 \le x \le 10^8$ ), the weight of a bar. Each of the following $p$ lines contains one integer $y$ ( $1 \le y \le 10^8$ ), the weight of a plate.

Output

Print every available lifting weight in increasing order, one per line. Do not print the same weight twice.

Examples5

Example 1

Input

Expected output

Example 2
Input
```
1 1
7
3
```
Expected output
```
7
```
Example 3
Input
```
1 2
10
4
4
```
Expected output
```
10
18
```
Example 4
Input
```
1 3
100
1
2
3
```
Expected output
```
100
106
```
Example 5
Input
```
2 2
10
12
1
1
```
Expected output
```
10
12
14
```