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 and each of them can transport a material if the material is within the reach of its jib. The cranes can rotate 360Β° and have a radius of reach .
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 representing the coordinates of a crane and its radius of reach (0 ≀ ≀ w) (0 ≀ ≀ h) and (0 ≀ ≀ 200).
The following line contains a single integer k (1 ≀ k ≀ 30) the number of destination points.
The next k lines contain 2 integers (0 ≀ ≀ w) (0 ≀ ≀ h) the destination coordinates.

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

To check your solution you need to sign in
Sign in to continue