Final Defense Line

たびたび未確認生物に侵略されるようになった某国では重要施設を新型防衛兵器で保護することにした。 この兵器は多角形の領域に特殊なガスを充満させることで未確認生物にダメージを与えることができる。未確認生物が侵攻する途中でガスの濃度が変わると、濃度の差の絶対値のダメージを与える。ガスの濃度が同じ領域を動いているときはダメージは一切発生しない。 現在の技術ではガスの濃度は一定にしかできないので、某国は新型防衛兵器を複数投入することにした。全ての兵器でガスの濃度は同じであり、複数の兵器の領域に含まれる部分は濃度が足し合わされる。 未確認生物の出現地点と重要施設の位置を元に、未確認生物が重要施設まで侵攻する時に受けるダメージの最小値を求めて欲しい。 ただし、未確認生物の侵攻ルートに多角形の頂点や他の多角形との交点は含まれないものとする。また、多角形の辺上を辺にそって侵攻することはない。

入力は以下の形式で与えられる。

多角形の数
多角形の頂点数
x座標 y座標
x座標 y座標
...
多角形の頂点数
x座標 y座標
x座標 y座標
...
出現地点と重要施設のデータの数
出現位置のx座標 出現位置のy座標 重要施設のx座標 重要施設のy座標
出現位置のx座標 出現位置のy座標 重要施設のx座標 重要施設のy座標
...

出現地点と重要施設の組ごとに未確認生物が重要施設まで侵攻する際に受けるダメージの最小値を1行ずつ出力せよ。

• 入力に含まれる座標は絶対値が1,000以下の整数
• 多角形の数は1以上5以下
• 多角形の頂点数は3以上5以下
• 出現地点と重要施設のデータの数は1以上100以下
• 多角形は与えられた頂点を順につないでできる多角形を指し、自己交差はない
• 出現地点と重要施設は多角形の頂点及び辺上にあることはない