Problem: In a country that has been frequently invaded by unidentified creatures, it has decided to protect important facilities with new defense weapons.
This weapon can damage unidentified creatures by filling a polygonal area with a special gas. If the concentration of gas changes during the invasion of an unidentified creature, it will cause damage with the absolute value of the difference in concentration. No damage occurs when the gas concentration is moving in the same area.
With current technology, the concentration of gas can only be kept constant, so a certain country decided to introduce multiple new defense weapons. The concentration of gas is the same for all weapons, and the concentrations of the parts contained in the territory of multiple weapons are added together. Based on the appearance point of unidentified creatures and the location of important facilities, please find the minimum value of damage that unidentified creatures will invade to important facilities.
However, the invasion route of unidentified organisms shall not include the vertices of polygons and intersections with other polygons. Also, it does not invade along the sides of the polygon.

Constraints

* The coordinates included in the input are integers with an absolute value of 1,000 or less.
* The number of polygons is 1 or more and 5 or less
* The number of vertices of a polygon is 3 or more and 5 or less
* The number of data of appearance points and important facilities is 1 or more and 100 or less
* A polygon refers to a polygon formed by connecting given vertices in order, and there is no self-intersection.
* Spawn points and important facilities are never on the vertices and sides of a polygon

Input

The input is given in the following format.

> Number of polygons
> Number of vertices of polygon
> x coordinate y coordinate
> x coordinate y coordinate
> ...
> Number of vertices of polygon
> x coordinate y coordinate
> x coordinate y coordinate
> ...
> Number of data on spawn points and important facilities
> X-coordinate of appearance position y-coordinate of appearance position x-coordinate of important facility y-coordinate of important facility
> X-coordinate of appearance position y-coordinate of appearance position x-coordinate of important facility y-coordinate of important facility
> ...
>

Output

Output the minimum value of damage that an unidentified creature invades to an important facility line by line for each group of spawn point and important facility.

Examples

Input

2
4
0 4
1 1
3 1
4 4
3
6 0
10 0
8 7
1
2 3 9 1


Output

2


Input

1
4
0 0
10 0
10 10
0 10
2
15 5 5 5
5 5 15 5


Output

1
1


Input

2
4
0 0
10 0
10 10
0 10
4
10 0
20 0
20 10
10 10
1
5 5 15 5


Output

0


Input

2
3
0 0
10 0
5 10
3
5 0
15 0
10 10
1
5 5 10 5


Output

2


Input

2
4
0 0
10 0
10 10
0 10
4
0 0
10 0
10 10
0 10
2
15 5 5 5
5 5 15 5


Output

2
2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
 
 
#define NUM 1005
 
struct Point{
    Point(double arg_x,double arg_y){
        x = arg_x;
        y = arg_y;
    }
 
    Point(){
        x = y = 0.0;
    }
 
    Point operator + (Point p){ return Point(x+p.x,y+p.y); }
    Point operator - (Point p){ return Point(x-p.x,y-p.y);}
    Point operator * (double a){ return Point(a*x,a*y); }
    Point operator / (double a){ return Point(x/a,y/a); }
 
    double abs(){ return sqrt(norm()); }
    double norm(){ return x*x + y*y; }
 
    bool operator<(const Point &p) const{
        return x != p.x? x < p.x: y < p.y;
    }
 
    bool operator == (const Point &p) const{
        return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
    }
 
    double x,y;
};
 
typedef Point Vector;
typedef vector<Point> Polygon;
 
struct Line{
    Point p[2];
    Line(Point p1,Point p2){
        p[0] = p1;
        p[1] = p2;
    }
    Line(){
 
    }
};
 
 
vector<Polygon> POLYGON,MAP;
vector<Line> LINE;
int table[NUM],min_dist[NUM][NUM];
bool is_adj[NUM][NUM];
 
 
double norm(Vector a){
    return a.x*a.x+a.y*a.y;
}
 
double abs(Vector a){
    return sqrt(norm(a));
}
 
double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}
 
double dot(Vector a,Vector b){
    return a.x*b.x + a.y*b.y;
}
 
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -1;
static const int ON_SEGMENT = 0;
 
int ccw(Point p0,Point p1,Point p2){
 
    Vector a = p1 - p0;
    Vector b = p2 - p0;
 
    if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
    if(cross(a,b) < -EPS)return CLOCKWISE;
    if(dot(a,b) < -EPS)return ONLINE_BACK;
    if(a.norm() < b.norm())return ONLINE_FRONT;
 
    return ON_SEGMENT;
}
 
/*
 * IN 2
 * ON 1
 * OUT 0
 *
 */
int contains(Polygon g,Point p){
    int n = g.size();
    bool x = false;
    for(int i = 0; i < n; i++){
        Point a = g[i]-p,b = g[(i+1)%n]-p;
        if(abs(cross(a,b)) < EPS && dot(a,b) < EPS)return 1;
        if(a.y > b.y)swap(a,b);
        if(a.y < EPS && EPS < b.y && cross(a,b) > EPS) x = !x;
    }
    return (x ? 2:0);
}
 
//交点を求める関数
Point calc_Cross_Point(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4){
    Point ret;
    ret.x = ((x2-x1)*(y3*(x4-x3)+x3*(y3-y4))-(x4-x3)*(y1*(x2-x1)+x1*(y1-y2)))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
    if(x1 != x2){
        ret.y = ((y2-y1)*ret.x+y1*(x2-x1)+x1*(y1-y2))/(x2-x1);
    }else{
        ret.y = ((y4-y3)*ret.x+y3*(x4-x3)+x3*(y3-y4))/(x4-x3);
    }
    return ret;
}
 
//インタフェース関数
Point calc_Cross_Point(Point a,Point b,Point c,Point d){
    return calc_Cross_Point(a.x,b.x,c.x,d.x,a.y,b.y,c.y,d.y);
}
 
Point calc_Cross_Point(Line A,Line B){
 
    return calc_Cross_Point(A.p[0],A.p[1],B.p[0],B.p[1]);
}
 
Polygon ConvexCut(Polygon g,Point a,Point b){
 
    Polygon ret;
    int N = g.size();
 
    for(int i = 0; i < g.size(); i++){
        Point A = g[i], B = g[(i+1)%N];
        if(ccw(a,b,A) != -1)ret.push_back(A);
        if(ccw(a,b,A)*ccw(a,b,B) == -1)ret.push_back(calc_Cross_Point(a,b,A,B));
    }
 
    return ret;
}
 
 
int main(){
 
    int N;
 
    scanf("%d",&N);
 
    int tmp;
 
    for(int loop = 0; loop < N; loop++){
 
        scanf("%d",&tmp);
 
        Polygon polygon;
 
        for(int i = 0; i < tmp; i++){
 
            double X,Y;
            scanf("%lf %lf",&X,&Y);
 
            polygon.push_back(Point(X,Y));
        }
        POLYGON.push_back(polygon);
    }
 
    //線分を先に作っておく
    for(int i = 0; i < N; i++){
        for(int k = 0; k < POLYGON[i].size(); k++){
 
            LINE.push_back(Line(POLYGON[i][k],POLYGON[i][(k+1)%POLYGON[i].size()]));
        }
    }
 
    //十分に大きい四角形でマップを囲む
    Polygon big_square;
 
    big_square.push_back(Point(NUM,NUM));
    big_square.push_back(Point(NUM,-NUM));
    big_square.push_back(Point(-NUM,-NUM));
    big_square.push_back(Point(-NUM,NUM));
 
    MAP.push_back(big_square);
 
    //領域の分割処理
    for(int i = 0; i < LINE.size(); i++){
 
        vector<Polygon> NEXT;
 
        for(int k = 0; k < MAP.size(); k++){
 
            Polygon polygon = ConvexCut(MAP[k],LINE[i].p[0],LINE[i].p[1]);
            if(polygon.size() >= 3){
 
                NEXT.push_back(polygon);
            }
            polygon = ConvexCut(MAP[k],LINE[i].p[1],LINE[i].p[0]);
            if(polygon.size() >= 3){
 
                NEXT.push_back(polygon);
            }
        }
        MAP = NEXT;
    }
 
    //領域の隣接関係を調べる
    for(int i = 0; i < MAP.size(); i++){
        for(int k = 0; k < MAP.size(); k++){
            if(k == i){
                is_adj[i][k] = true;
                continue;
            }
 
            bool FLG = false;
 
            //同じ辺を共有しているか調べる
            for(int a = 0; a < MAP[i].size(); a++){
                for(int b = 0; b < MAP[k].size(); b++){
 
                    Line A = Line(MAP[i][a],MAP[i][(a+1)%MAP[i].size()]);
                    Line B = Line(MAP[k][b],MAP[k][(b+1)%MAP[k].size()]);
 
                    if((abs(A.p[0]-B.p[0]) < EPS && abs(A.p[1]-B.p[1]) < EPS) || (abs(A.p[0]-B.p[1]) < EPS && abs(A.p[1]-B.p[0]) < EPS)){
 
                        FLG = true;
                        break;
                    }
                }
                if(FLG)break;
            }
 
            is_adj[i][k] = FLG;
        }
    }
 
    for(int i = 0; i < MAP.size(); i++){
 
        Vector vec;
        for(int k = 0; k < MAP[i].size(); k++){
 
            vec = vec+MAP[i][k];
        }
        vec = vec/MAP[i].size();
 
        int count = 0;
 
        for(int k = 0; k < POLYGON.size(); k++){
 
            if(contains(POLYGON[k],vec) == 2){
 
                count++;
            }
        }
        table[i] = count;
    }
 
 
 
    for(int i = 0; i < MAP.size(); i++){
        for(int k = 0; k < MAP.size(); k++){
            if(k != i){
 
                if(is_adj[i][k]){
 
                    min_dist[i][k] = abs(table[i]-table[k]);
 
                }else{
                    min_dist[i][k] = BIG_NUM;
                }
            }else{
 
                min_dist[i][k] = 0;
            }
        }
    }
 
    for(int mid = 0; mid < MAP.size(); mid++){
        for(int st = 0; st < MAP.size(); st++){
            if(min_dist[st][mid] == BIG_NUM)continue;
            for(int gl = 0; gl < MAP.size(); gl++){
                if(min_dist[mid][gl] == BIG_NUM)continue;
 
                min_dist[st][gl] = min(min_dist[st][gl],min_dist[st][mid]+min_dist[mid][gl]);
            }
        }
    }
 
    int num_query;
    scanf("%d",&num_query);
 
    int start = -1,goal = -1;
    Point enemy,building;
 
    for(int loop = 0; loop < num_query; loop++){
 
        scanf("%lf %lf %lf %lf",&enemy.x,&enemy.y,&building.x,&building.y);
 
        for(int i = 0; i < MAP.size(); i++){
 
            if(contains(MAP[i],enemy) >= 1){
                start = i;
                break;
            }
        }
        for(int i = 0; i < MAP.size(); i++){
 
            if(contains(MAP[i],building) >= 1){
 
                goal = i;
                break;
            }
        }
        printf("%d\n",min_dist[start][goal]);
    }
 
    return 0;
}