N Cities

SUST SWE 222 Lab 1
Limits 1s, 512 MB

In a country there are NN cities numbered from 11 to NN. To Travel along the cities there are total N bi directional roads. For each city numbered ii (1i<N1 \le i < N) there is a bi-directional road between city i and city i+1i+1. Furthermore, there is a road between city NN and city 11. 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 ii to city jj if there is a road between these two cities. Now initially you will be given the address of MM people. That is, for every people ii you will be given an integer aia_i, the city where ithi^{th} person lives. Then There will be QQ queries. In each query you will be given an integer XX. You will have to tell the total time that is required for all people to travel from their city to city XX. Now as we know everyone hates long time travelling, they will take the shortest path to travel from their cities to city XX.

Input

On the first line, there will be two integers NN (3N1093 ≤ N ≤ 10^9) and MM (1M2×1051 ≤ M ≤ 2×10^5) described in statement. Then the next MM line will contain one number each, ithi^{th} of them will be aia_i (1aiN1 ≤ a_i ≤ N), the number of the city where ithi^{th} person lives. Then there will be an integer QQ (1Q1051 ≤ Q ≤ 10^5), the number of queries. Then the following QQ lines will contain one integer XX (1XN1 ≤ X ≤ N) each, the number (ID) of destination city described in statement.

Output

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

Sample

InputOutput
10 2
2
9
2
10
5
3
7

Submit

Login to submit.

Contributors

Statistics

26% Solution Ratio
steinumEarliest, Dec '20
Deshi_TouristFastest, 0.0s
steinumLightest, 4.8 MB
steinumShortest, 1220B
Toph uses cookies. By continuing you agree to our Cookie Policy.