In the waiting room at the station there are N rows of M seats. So that those who are waiting do not get bored, K powerful Wi-Fi routers are installed instead of some chairs. Those who are waiting try to take places closer to the routers, as then they will be able to watch videos from Youtube or VK with a higher resolution, without delay. If the passenger is seated in seat number c in row r, and the i-th router is seated in seat Ci in row Ri, then the distance to the i-th router is calculated as max(|r−Ri|,|c−Ci|), where |x| – the absolute value of x. Seats in the waiting room were given priority from 1 to N⋅M−K, smaller numbers received seats with a shorter distance to the nearest router, among seats with the same distance to routers, the seats in the row with the smaller number are considered more comfortable, and among them &mdash ; with the lower number in the row. The figure shows seat priority in a waiting room with 4 rows of 7 seats, in which 2 routers are installed (their positions are marked in black). Armchairs located at a distance of 1 from the routers are highlighted in dark gray, light gray — at a distance of 2, white — 3.
Write a program that calculates the distance to the nearest router from a chair with some given priority.
The first line of input contains four integers — number of rows N (2 ≤ N ≤ 109) and seats in row M (2 ≤ M ≤ 109), number of routers K (1 ≤ K < 100, K < N⋅ M), number of requests Q (1 < Q < 100). This is followed by K lines containing two integers — location of routers: row number Ri (1 ≤ Ri ≤ N) and location number in row Ci (1 ≤ Сi ≤M). None of them match. This is followed by a line containing Q integers ranging from 1 to N⋅M−K – seat priorities.
Output for each query on a separate line one integer — distance to the nearest router from a chair with a given priority.
| Input |
Output |
|
4 7 2 4
2 5
4 4
1 6 16 26
|
1
1
2
3
|