smart-seating-plan

Gautam Buddha University examination team decided to drastically lower number of students from cheating by devising a wicked seating plan.
It was observed earlier that specific students from each batch were usually caught using unfair means.

Assume there are R rooms from 1 to R and B batches.
Now before doing usual arrangement, in each batch these students were assigned different rooms, from P to Q (both included) continuously.

After this plan was successfully generated, examination team wanted to check - how many rooms have atleast S number of such students?
They want to check this N number of times. 

Input:
First line contains R, number of rooms.
Second Line contains B, number of batches, followed by B Lines.
Each of next B lines contain 2 space separated integers P and Q.  

Next line contains N, number of queries.
Each of these N lines contain integer S (Minimum Number Of such Students for that query)

Output:
For each check, output number of rooms in new line.

Constraints:
1 ≤ R ≤ 1000000
1 ≤ B ≤ 1000000
1 ≤ P ≤ Q ≤ R
1 ≤ N ≤ 1000000
1 ≤ S ≤ N  

SAMPLE INPUT
4
3
1 3
2 3
1 4
3
1
3
2

SAMPLE OUTPUT
4
2
3

Explanation

We have 4 rooms, so we have array of 4 numbers (0,0,0,0)
Now after Batch 1 (1 3) it becomes (1,1,1,0)
After Batch 2 (2 3) it becomes (1,2,2,0)
After Batch 3 (1 4) it becomes (2,3,3,1)

Now for First check (Minimum 1) we have 4 rooms.
Now for second check (Minimum 3) we have 2 rooms.
Now for Third check (Minimum 2) we have 3 rooms.

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: