Problem2571--Gears

2571: Gears

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two polygons on the plane, A and B. Polygon A rotates around point P, and polygon B rotates around point Q. Each polygon rotates with the constant rotational speed in the clockwise direction around its point, the rotational speed values of the polygons' rotation are equal.

Your task is to determine if there will be a collision between polygons. A collision is a situation when the polygons have at least one common point.

It is guaranteed that at the moment 0 the polygons A and B do not intersect and no polygon is fully contained inside another one.

Note that:

  • the polygons are not necessarily convex;
  • points P and Q can be located on the border of or outside their polygons.
Input

The first line contains space-separated coordinates of point P.

The second line contains a single integer n (3≤n≤1000)− the number of vertices of polygon A.

Each of the next n lines contains two space-separated integers − the coordinates of the corresponding vertex of polygon A.

The next line is empty.

Then follow space-separated coordinates of point Q.

The next line contains a single integer m (3≤m≤1000)− the number of vertices of polygon B. Next m lines contain the coordinates of the vertices of the polygon B.

The vertices of both polygons are listed in the counterclockwise order. Coordinates of all points are integers, their absolute values don't exceed 104.

Output

Print "YES", if the collision takes place and "NO" otherwise (don't print the quotes).

Examples
Input
1 0
4
0 0
1 0
1 5
0 5

9 0
4
9 0
9 -5
10 -5
10 0
Output
YES
Input
0 0
3
1 0
2 -1
2 1

0 0
3
-1 0
-2 1
-2 -1
Output
NO
Note

A polygon is a closed polyline that doesn't intersect itself and doesn't touch itself.

Picture to the first sample:

Source/Category