Problem: Background

The kindergarten attached to the University of Aizu is a kindergarten where children who love programming gather. Yu, one of the kindergarten children, loves darts as much as programming. Yu-kun was addicted to darts recently, but he got tired of ordinary darts, so he decided to make his own darts board.

See darts for darts.

Problem

The contents of the darts that Yu-kun thought about are as follows.

The infinitely wide darts board has several polygons with scores. The player has only one darts arrow. The player throws an arrow and stabs the arrow into one of the polygons to get the score written there. If you stab it in any other way, you will not get any points.

Yu-kun decided where to throw the arrow, but it doesn't always stick exactly. The darts board is a two-dimensional plane, and the position Yu-kun is aiming for is a point (cx, cy). The place where the arrow thrown by Yu-kun sticks is selected with a uniform probability from any point included in the circle with radius r centered on the point (cx, cy). The coordinates of the exposed points do not have to be integers.

Since the information on the darts board, the position (cx, cy) that Yu-kun aims at, and the radius r are given, answer the expected value of the score that Yu-kun can get.

Constraints

The input satisfies the following conditions.

* All inputs are given as integers
* 1 ≤ n ≤ 50
* 0 ≤ cx, cy, x, y ≤ 1000
* 1 ≤ r ≤ 100
* 3 ≤ p ≤ 10
* 1 ≤ score ≤ 100
* Polygon vertices are given in such an order that they visit adjacent vertices clockwise or counterclockwise.
* The sides of a polygon do not have anything in common with the sides of another polygon
* A polygon does not contain another polygon
* If the arrow sticks on the side of the polygon, no score will be given.

Input


n cx cy r
Information on the 0th polygon
Information on the first polygon
...
Information on the (n-1) th polygon


n is the number of polygons on the darts board. Polygonal information is given in the following format.


p score
x0 y0
x1 y1
...
x (p-1) y (p-1)


p represents the number of vertices of the polygon, and score represents the score written on the polygon. Each line segment of the polygon is a line segment connecting the vertices of (xi, yi) and (xi + 1, yi + 1) (i <p-1), and (xp-1, yp-1) and (x0, It is a line segment connecting the vertices of y0).

Output

Output the expected value of the score that Yu-kun can get in one line. Any number of digits after the decimal point may be output. However, the error in the answer must not exceed 0.000001 (10-6).

Examples

Input

1 2 2 1
4 1
0 0
2 0
2 2
0 2


Output

0.2500000000


Input

1 2 2 1
4 1
0 0
5 0
5 5
0 5


Output

1.0000000000


Input

4 3 3 2
3 1
1 1
3 3
1 5
4 2
2 0
5 0
4 2
3 2
3 3
4 3
6 1
6 5
4 4
3 4
4 4
5 6
2 6


Output

1.0574955319


Input

1 10 10 1
4 10
0 0
1 0
1 1
0 1


Output

0.0000000000

Solution (in CPP):

Solution:
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

constexpr double EPS = 1e-9;

struct point {
	double x, y;
	explicit point(double x_ = 0.0, double y_ = 0.0):x(x_), y(y_) {}
	point(const point &p):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);
	}

	point operator* (double s) const {
		return point(x * s, y * s);
	}

	point operator* (const point &p) const {
		return point(x * p.x - y * p.y, x * p.y + y * p.x);
	}

	point operator/ (double s) const {
		return point(x / s, y / s);
	}

	bool operator< (const point &p) const {
		return x + EPS < p.x || (abs(x - p.x) < EPS && y + EPS < p.y);
	}

	bool operator== (const point &p) const {
		return abs(x - p.x) < EPS && abs(y - p.y) < EPS;
	}
};

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

double abs(const point &p) {
	return sqrt(norm(p));
}

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

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

struct line {
	point a, b;
	line(const point &a_, const point &b_):a(a_), b(b_){}
};

struct circle {
	point c;
	double r;
	circle(const point &c_, const double &r_):c(c_), r(r_){}
};

typedef vector<point> polygon;

int ccw(const point &a, point b, point c) {
	b = b - a;
	c = c - a;
	const double tmp = cross(b, c);
	if(tmp > EPS) return 1; // ccw
	if(tmp < -EPS) return -1; // cw
	if(dot(b, c) < 0) return 2; // c, a, b 順に一直線上
	if(norm(b) < norm(c)) return -2; // a, b, c 順に一直線上
	return 0; //a, c, b 順で一直線上
}

point project(const line &l, const point &p) {
	const point dif = l.b - l.a;
	const double tmp = dot(p - l.a, dif) / norm(dif);
	return l.a + dif * tmp;
}

vector<point> crosspoint(const circle &c, const line &l) {
	vector<point> res;
	const point h = project(l, c.c);
	const double d = abs(h - c.c);
	if(d > c.r + EPS) {
		// nothing
	}
	else if(d > c.r - EPS) {
		res.emplace_back(h);
	}
	else if(d <= c.r - EPS) {
		point v = l.b - l.a;
		v = v * sqrt(c.r * c.r - d * d) / abs(v);
		res.emplace_back(h - v);
		res.emplace_back(h + v);
	}

	return res;
}

double rad(const point &a, const point &b) {
	const int c = ccw(point(0, 0), a, b);
	if(abs(c) != 1) return 0;
	const double res = acos(dot(a, b) / (abs(a) * abs(b)));
	return c * res;
}

double area(circle c, point a, point b) {
	a = a - c.c;
	b = b - c.c;
	c.c = c.c - c.c;

	const auto cp = crosspoint(c, line(a, b));
	if(cp.size() == 0) return c.r * c.r * rad(a, b) / 2;

	const bool b1 = abs(a) > c.r + EPS;
	const bool b2 = abs(b) > c.r + EPS;

	if(b1 && b2) {
		if(dot(a - cp.front(), b - cp.front()) < EPS && dot(a - cp.back(), b - cp.back()) < EPS) {
			return (c.r * c.r * (rad(a, b) - rad(cp.front(), cp.back()))
					+ cross(cp.front(), cp.back())) / 2;
		}
		else {
			return c.r * c.r * rad(a, b) / 2;
		}
	}
	else if(b1) {
		return (c.r * c.r * rad(a, cp.front()) + cross(cp.front(), b)) / 2;
	}
	else if(b2) {
		return (c.r * c.r * rad(cp.back(), b) + cross(a, cp.back())) / 2;
	}
	else {
		return cross(a, b) / 2;
	}
}

double area(const circle &c, const polygon &P) {
	double res = 0.0;
	point prev = P.back();

	for(const auto &curr : P) {
		res += area(c, prev, curr);
		prev = curr;
	}

	return abs(res);
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(10);

	int n, cx, cy, r;
	cin >> n >> cx >> cy >> r;

	const circle c(point(cx, cy), r);
	const double all = c.r * c.r * M_PI;

	double ans = 0.0;
	for(int i = 0; i < n; ++i) {
		int m, score;
		cin >> m >> score;

		polygon P;
		P.reserve(m);
		for(int j = 0; j < m; ++j) {
			int x, y;
			cin >> x >> y;
			P.emplace_back(x, y);
		}

		const double s = area(c, P);
		ans += s / all * score;
	}

	cout << ans << endl;

	return EXIT_SUCCESS;
}