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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from math import acos, hypot, isclose, sqrt

def intersection(circle, polygon):
	(x, y, r) = circle
	polygon = [(xp - x, yp - y) for (xp, yp) in polygon]
	area = 0.0
	for (p1, p2) in zip(polygon, polygon[1:] + [polygon[0]]):
		ps = seg_intersection((0, 0, r), (p1, p2))
		for (pp1, pp2) in zip([p1] + ps, ps + [p2]):
			c = cross(pp1, pp2)
			if c == 0:
				continue
			d1 = hypot(*pp1)
			d2 = hypot(*pp2)
			if le(d1, r) and le(d2, r):
				area += c / 2
			else:
				t = acos(dot(pp1, pp2) / (d1 * d2))
				sign = 1.0 if c >= 0 else -1.0
				area += sign * r * r * t / 2
	return area

def cross(v1, v2):
	(x1, y1) = v1
	(x2, y2) = v2
	return x1 * y2 - x2 * y1

def dot(v1, v2):
	(x1, y1) = v1
	(x2, y2) = v2
	return x1 * x2 + y1 * y2

def seg_intersection(circle, seg):
	(x0, y0, r) = circle
	(p1, p2) = seg
	(x1, y1) = p1
	(x2, y2) = p2
	p1p2 = (x2 - x1) ** 2 + (y2 - y1) ** 2
	op1 = (x1 - x0) ** 2 + (y1 - y0) ** 2
	rr = r * r
	dp = dot((x1 - x0, y1 - y0), (x2 - x1, y2 - y1))
	d = dp * dp - p1p2 * (op1 - rr)
	ps = []
	if isclose(d, 0.0, abs_tol=1e-09):
		t = -dp / p1p2
		if ge(t, 0.0) and le(t, 1.0):
			ps.append((x1 + t * (x2 - x1), y1 + t * (y2 - y1)))
	elif d > 0.0:
		t1 = (-dp - sqrt(d)) / p1p2
		if ge(t1, 0.0) and le(t1, 1.0):
			ps.append((x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)))
		t2 = (-dp + sqrt(d)) / p1p2
		if ge(t2, 0.0) and le(t2, 1.0):
			ps.append((x1 + t2 * (x2 - x1), y1 + t2 * (y2 - y1)))
	return ps

def le(f1, f2):
	return f1 < f2 or isclose(f1, f2, abs_tol=1e-09)

def ge(f1, f2):
	return f1 > f2 or isclose(f1, f2, abs_tol=1e-09)
(N, cx, cy, r) = map(int, input().split())
ans = 0
from math import pi
circle_area = pi * r * r
for _ in range(N):
	(p, score) = map(int, input().split())
	ps = []
	for _ in range(p):
		(x, y) = map(int, input().split())
		ps.append((x, y))
	area = intersection((cx, cy, r), ps)
	ans += abs(area) * score / circle_area
print(f'{ans:.10f}')