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 <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

using namespace std;

template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

// * geometry library

typedef double Real;
constexpr Real EPS = 1e-8;
inline int sign(Real d) { return d > EPS ? 1 : d < -EPS ? -1 : 0; }

struct point {
	Real x, y;
	explicit point():x(0), y(0) {}
	explicit point(Real x_, Real y_):x(x_), y(y_) {}
	point operator+(const point &p) const { return point(x + p.x, y + p.y); }
	point operator-(const point &p) const { return point(x - p.x, y - p.y); }
	point operator*(const point &p) const { return point(x * p.x - y * p.y, x * p.y + y * p.x); }
	point operator*(Real s) const { return point(x * s, y * s); }
	point operator/(Real s) const { return point(x / s, y / s); }
	bool operator<(const point &p) const { return sign(x - p.x) == -1 || (sign(x - p.x) == 0 && sign(y - p.y) == -1); }
	bool operator>(const point &p) const { return sign(x - p.x) == 1 || (sign(x - p.x) == 0 && sign(y - p.y) == 1); }
	bool operator==(const point &p) const { return sign(x - p.x) == 0 && sign(y - p.y) == 0; }
	bool operator!=(const point &p) const { return sign(x - p.x) != 0 || sign(y - p.y) != 0; }
};

inline istream &operator>>(istream &is, point &p) {
	return is >> p.x >> p.y;
}

inline ostream &operator<<(ostream &os, const point &p) {
	return os << '(' << p.x << ", " << p.y << ')';
}

struct segment : public array<point, 2> {
	segment(const point &a, const point &b) { at(0) = a; at(1) = b; }
};

typedef vector<point> polygon;

inline Real angle(const point &p) {
	return atan2(p.y, p.x);
}

inline Real norm(const point &p) {
	return p.x * p.x + p.y * p.y;
}

inline Real dot(const point &a, const point &b) {
	return a.x * b.x + a.y * b.y;
}

inline Real cross(const point &a, const point &b) {
	return a.x * b.y - a.y * b.x;
}

enum { CCW = 1, CW = -1, BACK = 2, FRONT = -2, ON = 0};
inline int ccw(const point &a, const point &b, const point &c) {
	const point p = b - a;
	const point q = c - a;
	const int sign_cross = sign(cross(p, q));
	if(sign_cross == 1) return CCW;
	if(sign_cross == -1) return CW;
	if(sign(dot(p, q)) == -1) return BACK;
	if(sign(norm(p) - norm(q)) == -1) return FRONT;
	return ON;
}

inline bool intersect(const segment &s, const point &p) {
	return ccw(s[0], s[1], p) == ON;
}

inline bool intersect(const segment &a, const segment &b) {
	return ccw(a[0], a[1], b[0]) * ccw(a[0], a[1], b[1]) <= 0
		&& ccw(b[0], b[1], a[0]) * ccw(b[0], b[1], a[1]) <= 0;
}

inline bool contain(const polygon &P, const point &p) {
	bool res = false;
	for(int i = 0; i < P.size(); ++i) {
		point v1 = P[i] - p;
		point v2 = P[(i + 1) % P.size()] - p;
		if(v1.y > v2.y) swap(v1, v2);
		if(sign(cross(v1, v2)) == 0 && sign(dot(v1, v2)) <= 0) return true; // on edge
		if(sign(v1.y) <= 0 && sign(v2.y) == 1 && sign(cross(v1, v2)) == 1) res = !res;
	}
	return res;
}

inline point crosspoint(const segment &a, const segment &b) {
	assert(intersect(a, b));
	const Real crs = cross(a[1] - a[0], b[1] - b[0]);
	if(sign(crs) == 0) { // on same line
		if(intersect(a, b[0])) return b[0];
		if(intersect(a, b[1])) return b[1];
		if(intersect(b, a[0])) return a[0];
		return a[1];
	}
	return b[0] + (b[1] - b[0]) * (cross(a[1] - a[0], a[1] - b[0]) / crs);
}

inline Real area(const polygon &P) {
	Real res = 0;
	for(int i = 0; i < P.size(); ++i) {
		res += cross(P[i], P[(i + 1) % P.size()]);
	}
	return abs(res) * 0.5;
}

inline void merge(vector<segment> &segments) {
	for(int i = 0; i < segments.size(); ) {
		const segment &s1 = segments[i];
		bool ok = true;
		for(int j = i + 1; j < segments.size(); ++j) {
			const segment &s2 = segments[j];

			if(intersect(s1, s2) && sign(cross(s1[0] - s1[1], s2[0] - s2[1])) == 0) {
				const point a = min({s1[0], s1[1], s2[0], s2[1]});
				const point b = max({s1[0], s1[1], s2[0], s2[1]});
				segments.emplace_back(a, b);
				segments.erase(segments.begin() + j);
				segments.erase(segments.begin() + i);
				ok = false;
				break;
			}
		}
		if(ok) ++i;
	}
}

struct edge {
	int to;
	Real theta;
	bool used;
	edge(int to_, Real theta_):to(to_), theta(theta_), used(false) {}
	bool operator<(const edge &e) const { return theta < e.theta; }
};

typedef vector<vector<edge>> graph;
graph arrangement(vector<segment> &segments, vector<point> &points) {
	merge(segments);
	const int n = segments.size();
	points.clear();

	for(int i = 0; i < n; ++i) {
		const segment &s1 = segments[i];
		points.emplace_back(s1[0]);
		points.emplace_back(s1[1]);

		for(int j = i + 1; j < n; ++j) {
			const segment &s2 = segments[j];
			if(intersect(s1, s2)) points.emplace_back(crosspoint(s1, s2));
		}
	}

	sort(begin(points), end(points));
	points.erase(unique(begin(points), end(points)), end(points));

	const int V = points.size();
	graph G(V);
	for(const segment &s : segments) {
		vector<pair<Real, int>> vs;
		for(int i = 0; i < V; ++i) {
			if(intersect(s, points[i])) vs.emplace_back(norm(s[0] - points[i]), i);
		}

		sort(begin(vs), end(vs));
		for(int i = 1; i < vs.size(); ++i) {
			const int v = vs[i].second;
			const int u = vs[i - 1].second;
			G[v].emplace_back(u, angle(points[u] - points[v]));
			G[u].emplace_back(v, angle(points[v] - points[u]));
		}
	}
	for(vector<edge> &edges : G) sort(begin(edges), end(edges));
	return G;
}

vector<polygon> find_faces(graph &G, const vector<point> &points) {
	vector<polygon> res;

	const int V = G.size();
	for(int i = 0; i < V; ++i) {
		for(int j = 0; j < G[i].size(); ++j) {
			int v = i;
			int e_idx = j;
			polygon P;

			while(true) {
				edge &e = G[v][e_idx];
				if(e.used) break;

				e.used = true;
				P.emplace_back(points[v]);
				for(int k = 0; k < G[e.to].size(); ++k) {
					if(G[e.to][k].to == v) {
						v = e.to;
						e_idx = (k + 1) % G[e.to].size();
						break;
					}
				}
			}
			if(P.size() >= 3) res.emplace_back(move(P));
		}
	}
	return res;
}
// * solve

point inner_point(const polygon &P) {
	const int n = P.size();
	for(int i = 0; i < n; ++i) {
		const point &a = P[i];
		const point &b = P[(i + 1) % n];
		const point &c = P[(i + 2) % n];
		if(sign(cross(b - a, c - a)) == 0) continue;
		const point p = (a + b + c) * (1.0 / 3.0);
		if(contain(P, p)) return p;
	}
	assert(false);
}

bool common_segment(const polygon &A, const polygon &B) {
	const int n = A.size();
	const int m = B.size();

	for(int i = 0; i < n; ++i) {
		point a1 = A[i];
		point a2 = A[(i + 1) % n];
		if(a1 > a2) swap(a1, a2);

		for(int j = 0; j < m; ++j) {
			point b1 = B[j];
			point b2 = B[(j + 1) % m];
			if(b1 > b2) swap(b1, b2);

			if(a1 == b1 && a2 == b2) return true;
		}
	}
	return false;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<segment> segments;
	vector<polygon> polygons;
	polygons.reserve(n);

	for(int i = 0; i < n; ++i) {
		int m;
		cin >> m;

		polygon P(m);
		for(auto &e : P) cin >> e;

		if(i) segments.emplace_back(polygons.back().front(), P.front());
		for(int j = 0; j < m; ++j) {
			segments.emplace_back(P[j], P[(j + 1) % m]);
		}

		polygons.emplace_back(move(P));
	}

	vector<point> points;
	graph G = arrangement(segments, points);
	const auto faces = find_faces(G, points);

	const int V = faces.size();

	int outside = -1;
	for(int i = 0; i < V; ++i) {
		if(sign(area(faces[i])) == 1) {
			outside = i;
			break;
		}
	}
	assert(outside != -1);

	vector<int> num(V, 0);
	for(int i = 0; i < V; ++i) {
		if(i == outside) continue;

		const point p = inner_point(faces[i]);
		for(const auto &P : polygons) {
			if(contain(P, p)) ++num[i];
		}
	}

	constexpr int INF = INT_MAX >> 1;
	vector<vector<int>> dist(V, vector<int>(V, INF));
	for(int i = 0; i < V; ++i) {
		dist[i][i] = 0;
		for(int j = i + 1; j < V; ++j) {
			if(!common_segment(faces[i], faces[j])) continue;
			dist[i][j] = dist[j][i] = abs(num[i] - num[j]);
		}
	}

	for(int k = 0; k < V; ++k) {
		for(int i = 0; i < V; ++i) {
			for(int j = 0; j < V; ++j) {
				chmin(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	int q;
	cin >> q;

	while(q--) {
		point s, t;
		cin >> s >> t;

		int si = outside, ti = outside;
		for(int i = 0; i < V; ++i) {
			if(i == outside) continue;
			if(contain(faces[i], s)) si = i;
			if(contain(faces[i], t)) ti = i;
		}
		cout << dist[si][ti] << '\n';
	}

	return EXIT_SUCCESS;
}