Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

N Cities

Limits 1s, 512 MB

In a country there are N cities numbered from 1 to N. To Travel along the cities there are total N bi directional roads. For each city numbered i (1 ≤ i < N) there is a bi-directional road between city i and city i+1. Furthermore, there is a road between city N and city 1. People can only use any of these roads to travel from a city to another. As travel technology of this country is very advanced, it requires only 1 second time to travel from city i to city j if there is a road between these two cities. Now initially you will be given the address of M people. That is, for every people i you will be given an integer ai, the city where ith person lives. Then There will be Q queries. In each query you will be given an integer X. You will have to tell the total time that is required for all people to travel from their city to city X. Now as we know everyone hates long time travelling, they will take the shortest path to travel from their cities to city X.

Input

On the first line, there will be two integers N and M described in statement. Then the next M line will contain one number each, ith of them will be ai, the number of the city where ith person lives. Then there will be an integer Q, the number of queries. Then the following Q lines will contain one integer X each, the number(id) of destination city described in statement.

Constraints:
3 ≤ N ≤ 109
1 ≤ M ≤ 2*105
1 ≤ ai ≤ N
1 ≤ Q ≤ 105
1 ≤ X ≤ N

Output

For each query print an integer, the total time that is required for all M people to travel from their city to city X.

Sample

InputOutput
10 2
2
9
2
10
5
3
7

    Discussion

    Statistics


    14% Solution Ratio

    steinumEarliest, 3w ago

    steinumFastest, 0.1s

    steinumLightest, 4.8 MB

    steinumShortest, 1220B

    Submit

    Login to submit