Flying Around 3-SATurn

After many years of training, Byteasar finally obtained his pilot license and now wishes to fly around the planet 3‐SATurn along its equator. However, due to the long circumference of the equator, he must refuel at many airports located along it. Byteasar has the positions of all the airports on the equator and wants to know, for each airplane model (with its own flight range), what is the minimum number of landings (including the final landing) required to complete a full circle. Note that the journey can start at any airport.

More formally, you are given the total length T of the equator, and N airports located at distinct positions along the equator (measured as distances in kilometers from an arbitrary 0 point, where 0 ≤ position < T). Then, you will be given Q queries. Each query consists of one integer R representing the flight range (the maximum distance an airplane can fly on a full tank). For each query, determine the minimum number of landings (stops at airports including the final one when completing the circle) required to cover a distance of T along the circle. If it is impossible to complete the journey because some gap between consecutive airports (in circular order) is greater than R, output -1.

Note on flight rules: Each flight leg must begin and end at an airport. When planning the route, you may choose to skip intermediate airports as long as the total distance between the departing airport and the landing airport (accumulating consecutive segments along the circle) does not exceed R. The journey is complete once the airplane returns to the starting airport having covered a total distance of T.

The answer for each query is independent, and note that the best starting airport (yielding the fewest landings) may differ for different flight ranges.

inputFormat

The input consists of the following:

1. An integer T (1 ≤ T ≤ 10⁹) representing the total length of the equator.
2. An integer N (1 ≤ N ≤ 10⁵) representing the number of airports.
3. A line with N space‐separated integers, each representing an airport's position on the equator (0 ≤ position < T). The positions are distinct but not necessarily sorted.
4. An integer Q (1 ≤ Q ≤ 10⁵) representing the number of queries.
5. Q lines follow, each containing an integer R (1 ≤ R ≤ 10⁹) representing the airplane's flight range for that simulation.

outputFormat

For each query, output a single line containing the minimum number of landings required to complete the journey, or -1 if it is impossible.

sample

100
5
0 10 30 60 80
3
30
35
40

4
4
3