Today Alice is teaching her bot Ave how to play games. So, here is the task for Ave to complete. Ave has to reach the target starting with some energy S and at position 0, he has to cover D distance. There are few energy centres in the path. Ave can use them to refill energy of amount C. Remember Ave will always refill his energy of amount C. But he has to use them wisely as he has to lessen the cost.Also note that that he could only traverse one unit distance with one unit of energy.
Edit: Ave would have C energy after leaving any energy center. Any left energy wouldn't matter at that point
Input:
First line contains D, N, C - the distance between starting point and the target, number of energy centres, amount of energy that can be filled through one energy centres
Second line contains N space-separated numbers denoting A1, A2, ....., AK denoting the position of energy centres
Third line contains Q, the number of queries
Next Q lines contains number S denoting the starting energy Ave is given
Output:
Print Q lines containing a number denoting the minimum number of energy stores Ave would stop at to refill his energy.
If its not possible then print "Not possible" without quotes.
Constraints:
1 ≤ D ≤ 2*105
1 ≤ N < D
0 ≤ C ≤ 10 5
1 ≤ Ai < D
1 ≤Q ≤ 105
0 ≤ S ≤ 2*105
For Query 2:
First ave will start with 5 units of energy. Since there is no energy centre at position 5 so, he have to fill his energy at position 3.
After that it will travel till 8th and since there is an energy centre at 8 he would refill his energy
After that he will require some energy at the 13th position but at that position there is no energy centre. So, he have to fill his energy at 12th position
After that he will have sufficient energy to reach the last position
So Ave would stop at 3 energy centres at minimum for this query.
