Problem A
Magical Cows

Image by Graeme Zinck, CC BY-SA

Baxter Scott owns The Enlightened Dairy Co., a dairy company with magical cows. Early each morning, he brushes his teeth, strolls outside, and finds that the cows have doubled in number. With double the number of cows, he can produce double the quantity of milk. While he is ecstatic that he has so many cows and so much milk, the Dairy Regulator forces him to keep at most $C$ cows on any given farm, which greatly complicates his business.

At The Enlightened Dairy Co., Baxter has access to an unlimited number of farms, each with a maximum capacity of $C$ cows. On each farm, cows reproduce at the same rate: they always double in number when the clock strikes midnight. To stay within the Regulator’s rules, whenever a farm has strictly more than $C$ cows, Baxter selects half of the cows on that farm and moves them to an entirely new, empty farm. More precisely, if there are $D \leq C$ cows on a farm, he leaves all $D$ cows on the farm, but if there are $D > C$ cows on a farm, he leaves $\left\lceil \frac{D}{2} \right\rceil $ cows on the farm and takes $\left\lfloor \frac{D}{2} \right\rfloor $ cows to a new, empty farm. (Here $\left\lceil \ \right\rceil $ and $\left\lfloor \ \right\rfloor $ denote the ceiling and floor functions, which round up/down to the nearest integer, respectively.) He does this early every morning, before the Regulator could possibly show up, so that he can avoid paying hefty Moo Fees.

The Regulator needs to know how many farms she will be inspecting when she visits The Enlightened Dairy Co. The Regulator inspects every farm that has at least one cow, and does not inspect any farm with zero cows. Given the number of cows on each farm with at least one cow on Day $0$, compute the number of farms that need inspecting on any given day.

Input

The first line of input contains three space-separated integers, $C$, $N$, and $M$, where $C$ ($1 \leq C \leq 1\, 000$) is the maximum number of cows allowed on a farm, $N$ ($0 \leq N \leq 1\, 000$) is the number of farms with at least one cow on Day $0$, and $M$ ($1 \leq M \leq 50$) is the number of different days on which the Regulator visits. The following $N$ lines of input each have a single integer $c_ i$ ($1 \leq c_ i \leq C$), representing the number of cows on the $i$th of the $N$ farms on Day $0$. The final $M$ lines each have a single integer $d_ j$ ($0 \leq d_ j \leq 50$), representing a day when the Regulator visits. All $d_ j$ are distinct.

Output

For each $d_ j$, output one line with a single integer: the number of farms the Regulator will inspect on Day $d_ j$.

1 5 5
1
1
1
1
1
0
1
2
3
4

5
10
20
40
80

2 5 3
1
2
1
2
1
0
1
2

5
7
14