Optimize the Construction Process
You have been hired by a construction company to optimize the process of moving heavy construction materials from one place to another.
The construction field has a rectangular area with width
w and height h. You can think of it as a rectangle that has the bottom left corner at the coordinate (0, 0) and the top-right coordinate at (w, h). The entrance is at the center of the bottom side of the construction site.There are
n cranes on the construction field at different locations Given several destination points, the company would like to know the minimum number of cranes required that would get the materials from the entrance to that point.
Input
The first line of the input contains two integers
w and h (2 ≤ w, h ≤ 200) where w is even.The next line contains a single integer
n (1 ≤ n ≤ 50) representing the number of cranes.The next
n lines contain 3 integers The following line contains a single integer
k (1 ≤ k ≤ 30) the number of destination points.The next
k lines contain 2 integers Output
The program should print
k lines each one containing the minimum number of cranes required to reach the destination point. If it’s not possible to reach a destination point, the program should print Impossible.Examples
Input | Output |
4 4
2
2 1 1
2 3 1
5
2 2
3 2
1 2
2 3
3 3 | 1
Impossible
Impossible
2
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB