B. BWS Baker Web Service
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Our super smart cat Baker has created a start-up which provides $$$N$$$ microservices which are deployed on various cloud hosts using BWS services. The start-up has been very successful and has started to grow in the user requests it receives. According to internal metrics, requests have doubled every month and it is estimated that this will continue for the next $$$54$$$ months.

To maintain the availability and latency of the services, each host should support maximum $$$C$$$ user requests. When the number of requests doubles ($$$D$$$) and exceeds the capacity $$$C$$$ a new host must be rented and the user traffic should be distributed as follows:

  • $$$ceil_{1000}$$$$$$(\frac{D}{2})$$$ requests are kept on the current hosts
  • $$$floor_{1000}$$$$$$(\frac{D}{2})$$$ requests will be redirected to the new host

Where $$$ceil_{1000}$$$ and $$$floor_{1000}$$$ means rounding up and down, respectively, to thousandths.

As BWS hosts are expensive, the financial department wants to forecasts costs and requires us to make a report for $$$M$$$ different months indicating in each month how many hosts will be rented. Given the number $$$N$$$ of microservices in the service and the number of requests that each microservices currently supports, calculate for each of the $$$M$$$ ($$$1 \leq M \leq 54$$$) months how many hosts should be rented to serve the traffic.

Input

The first line of input contains three space-separated integers, $$$C$$$, $$$N$$$ and $$$M$$$ where $$$C$$$ ($$$1000 \leq C \leq 10^6$$$) is the maximum number of requests allowed by each host, $$$N$$$ ( $$$0 \leq N \leq 1000$$$) is the number of microservices, and $$$M$$$ the number of months on which the accounting department wants the report. Each of the following $$$N$$$ lines contains a single integer $$$n_i$$$ ($$$0 \lt n_i \leq C$$$) representing the number of current requests (month 0) for each microservice.

Each of the following $$$M$$$ lines contains a single integer $$$m_i$$$ ( $$$0 \leq m_i \leq 54$$$), representing a month the financial department needs to be included in the report.

Output

Print $$$M$$$ lines, where the $$$i$$$-th line represents the number of hosts rented to support traffic on the $$$m_i$$$-th month.

Examples
Input
1000 5 5
1000
1000
1000
1000
1000
0
1
2
3
4
Output
5
10
20
40
80
Input
2000 5 3
1000
2000
1000
2000
1000
1
0
2
Output
7
5
14