Problem A

Aha, you may have found a solution to the zombie apocalypse! All zombies want to do is eat brains, so why not synthesize your own?

You have come up with a new recipe for a plant-based brain substitute and have begun mass production. Orders from other strongholds are pouring in.

An infinite supply of shipping containers is available, and each can hold a specific number of brain substitutes. These substitutes are delicate; each container should be perfectly packed in order to ensure the brains do not roll around and get bruised during transportation.

Unfortunately, not every order can be satisfied through an exact packing of containers. While you do have an infinite supply of shipping containers, you do not have access to any packing foam during the zombie apocalypse. Orders that cannot be satisfied by sending perfectly packed shipping containers will incur a small delay while you hunt down packing foam.

For example, if the only sizes of shipping containers you have access to can hold either $4$ brain substitutes or $5$ brain substitutes, then it would be impossible to fulfill an order for $11$ brain substitutes by sending perfectly packed shipping containers. But it is possible to satisfy an order for $13$ brain substitutes: send $2$ containers of size $4$ and $1$ container of size $5$.

Your task is the following. Given the sizes of shipping containers at your disposal and sizes of various orders for brain substitutes, you should determine which orders can be satisfied at once by perfectly packing shipping containers and which orders will be delayed while you hunt down packing foam.


The first line of input contains two integers $N$ ($1 \leq N \leq 20$) and $M$ ($1 \leq M \leq 10^5$).

The second line contains $N$ integers $s_1, s_2, \ldots , s_ N$ ($1 \leq s_ i \leq 10^5$ for each $1 \leq i \leq N$). These are the sizes of the shipping containers you have access to. Remember, you have an infinite supply of each size of shipping container.

The last line contains $M$ integers $b_1, b_2, \ldots , b_ M$ ($1 \leq b_ i \leq 10^{15}$ for each $1 \leq i \leq M$) indicating that the $i$th order has requested $b_ i$ brain substitutes.


Output a single line containing $M$ integers $a_1, a_2, \ldots , a_ M$. For each $1 \leq i \leq M$, if some selection of containers has size exactly $b_ i$, then $a_ i$ should be $1$. Otherwise, $a_ i$ should be $0$.

Sample Input 1 Sample Output 1
2 7
5 4
4 11 12 13 5 8 6
1 0 1 1 1 1 0
Sample Input 2 Sample Output 2
1 10
1 2 3 4 5 6 7 8 9 10
0 1 0 1 0 1 0 1 0 1
Sample Input 3 Sample Output 3
5 10
14 21 99 17 14
67 43 101 98909878294 12 41124 1 67 67 9128
0 0 1 1 0 1 0 0 0 1

Please log in to submit a solution to this problem

Log in