建設プロセスの最適化
大きな建設資材をある場所から別の場所へ運ぶ作業を効率化するために、あなたは建設会社に雇われました。
現場は幅
w、高さ h の長方形の敷地です。左下の座標が (0, 0)、右上の座標が (w, h) の長方形と考えられます。敷地の入口は、底辺の中央（下辺の中央部分）にあります。敷地内には
n 台のクレーンが、それぞれ の位置に設置されています。クレーンはジブ（アーム）内に資材が入っていれば、その資材を運ぶことができます。クレーンは360°旋回が可能で、それぞれ の半径内であれば作業が可能です。複数の目的地が与えられたとき、入口からその目的地まで資材を運ぶために必要な最小のクレーン台数を知りたいと考えています。
入力
最初の行には2つの整数
w と h (2 ≤ w, h ≤ 200) が与えられます。ここで w は偶数です。次の行には、クレーンの台数
n (1 ≤ n ≤ 50) が1つの整数として与えられます。続く
n 行には、クレーンの座標とその作業範囲の半径を表す3つの整数 が与えられます。ここで、(0 ≤ ≤ w)、(0 ≤ ≤ h)、(0 ≤ ≤ 200) を満たします。さらにその次の行には、目的地の数
k (1 ≤ k ≤ 30) を示す1つの整数が与えられます。続く
k 行には、目的地の座標を示す2つの整数 (0 ≤ ≤ w, 0 ≤ ≤ h) が与えられます。出力
答えとして、
k 行を出力します。それぞれの目的地について、入口からそこへ到達するために必要な最小のクレーン台数を1行に出力してください。もし、その目的地に到達することができない場合は、"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