Spotlight Movement

Time limit2sMemory limit512 MB

Summary

Given N spotlights whose centers move around polygonal orbits, decide whether Ciel can walk from a start point to an end point while staying inside at least one illuminated circle at all times.

Level: Hard8 of 10
Topics: Geometry, Simulation, Graph, Union-find
Solved: No attempts yet

Problem

Ciel, an idol whose appearance and behavior resemble a fox, is taking part in a rehearsal for a live concert that happens in a few days. Becoming a top idol takes a lot of effort!

The live stage can be represented as a two-dimensional plane. The stage has N spotlights that illuminate it. The i-th spotlight casts light over a circle of radius ri. The center of the light cast by the i-th spotlight moves along an orbit Ri. Ri is given as a closed polygon, and Ri may contain self-intersections. The spotlight starts moving from the first vertex of Ri. Every spotlight has the same orbital period. Each spotlight moves at constant speed, and all of them return to their starting point at the same time.

In the rehearsal, Ciel must move from the starting point marked on the stage to the ending point. To reach her goal, she must not leave the area illuminated by the spotlights. While she stands on the starting point, however, she does not have to be illuminated. Assume she can move fast enough. Answer whether she can reach the ending point.

Input

Each input dataset is given in the following format:

N sx sy ex ey
r1 K1 x11 y11 x12 y12 ... x1K1 y1K1
r2 K2 x21 y21 x22 y22 ... x2K2 y2K2
:
:
rN KN xN1 yN1 xN2 yN2 ... xNKN yNKN

All input is integer. All coordinate information satisfies -10,000 ≤ x, y ≤ 10,000. N (1 ≤ N ≤ 100) is the number of spotlights. (sx, sy) and (ex, ey) are the starting point and the ending point of Ciel's path, respectively. The following N lines describe each spotlight. ri (1 ≤ ri ≤ 100) is the radius of the spotlight, and Ki (2 ≤ Ki ≤ 10) is the number of vertices in the orbit. Then Ki vertices are given. Two consecutive vertices on the same orbit are at different positions. The spotlight moves from the first point (xi1, yi1) to the second point (xi2, yi2), then to the third point (xi3, yi3), and so on. After moving to the Ki-th point (xiKi, yiKi), the spotlight returns to the first point (xi1, yi1) and repeats the same movement.

Let dij be the closest distance between the center of spotlight i and the center of spotlight j. dij satisfies one of the following:

dij > ri + rj + 0.000001
dij < ri + rj - 0.000001

Also, let di be the closest distance between the center of spotlight i and either the starting point or the ending point. di satisfies one of the following:

di > ri + 0.000001
di < ri - 0.000001

Output

If Ciel can reach the ending point without leaving the illuminated area, output Yes on one line. Otherwise, output No.

Examples4

Example 1

Input

2 1 1 9 -1
2 2 1 1 -9 1
1 2 -1 -1 9 -1

Expected output

Yes

Example 2

Input

2 1 1 9 -1
2 2 1 1 -9 1
1 2 9 -1 -1 -1

Expected output

No

Example 3

Input

2 11 6 -9 1
6 4 10 5 10 0 5 0 5 5
5 4 -10 0 -10 5 -5 5 -5 0

Expected output

Yes

Example 4
Input
```
1 1 9999 -1 0
100 2 0 0 0 10000
```
Expected output
```
Yes
```