No tag edit access

D. Gears

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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 10^{4}.

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:

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2017 10:05:29 (c5).

Desktop version, switch to mobile version.

User lists

Name |
---|