Cowboy Beblop is a funny little boy who likes sitting at his computer. He somehow obtained two elastic hoops in the shape of 2D polygons, which are not necessarily convex. Since there's no gravity on his spaceship, the hoops are standing still in the air. Since the hoops are very elastic, Cowboy Beblop can stretch, rotate, translate or shorten their edges as much as he wants.

For both hoops, you are given the number of their vertices, as well as the position of each vertex, defined by the X , Y and Z coordinates. The vertices are given in the order they're connected: the 1st vertex is connected to the 2nd, which is connected to the 3rd, etc., and the last vertex is connected to the first one. Two hoops are connected if it's impossible to pull them to infinity in different directions by manipulating their edges, without having their edges or vertices intersect at any point – just like when two links of a chain are connected. The polygons' edges do not intersect or overlap. 

To make things easier, we say that two polygons are well-connected, if the edges of one polygon cross the area of the other polygon in two different directions (from the upper and lower sides of the plane defined by that polygon) a different number of times.

Cowboy Beblop is fascinated with the hoops he has obtained and he would like to know whether they are well-connected or not. Since he’s busy playing with his dog, Zwei, he’d like you to figure it out for him. He promised you some sweets if you help him! 


-----Input-----

The first line of input contains an integer n (3 ≤ n ≤ 100 000), which denotes the number of edges of the first polygon. The next N lines each contain the integers x, y and z ( - 1 000 000 ≤ x, y, z ≤ 1 000 000) — coordinates of the vertices, in the manner mentioned above. The next line contains an integer m (3 ≤ m ≤ 100 000) , denoting the number of edges of the second polygon, followed by m lines containing the coordinates of the second polygon’s vertices.

It is guaranteed that both polygons are simple (no self-intersections), and in general that the obtained polygonal lines do not intersect each other. Also, you can assume that no 3 consecutive points of a polygon lie on the same line.


-----Output-----

Your output should contain only one line, with the words "YES" or "NO", depending on whether the two given polygons are well-connected. 


-----Example-----
Input
4
0 0 0
2 0 0
2 2 0
0 2 0
4
1 1 -1
1 1 1
1 3 1
1 3 -1

Output
YES



-----Note-----

On the picture below, the two polygons are well-connected, as the edges of the vertical polygon cross the area of the horizontal one exactly once in one direction (for example, from above to below), and zero times in the other (in this case, from below to above). Note that the polygons do not have to be parallel to any of the xy-,xz-,yz- planes in general. [Image]

Source: codeforces | Difficulty: VERY_HARD
Tags: Geometry


Solutions:
from math import gcd, sqrt
from functools import reduce
import sys
input = sys.stdin.readline
EPS = 1e-10

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def GCD(args):
	return reduce(gcd, args)

def plane_value(plane, point):
	(A, B, C, D) = plane
	(x, y, z) = point
	return A * x + B * y + C * z + D

def plane(p1, p2, p3):
	(x1, y1, z1) = p1
	(x2, y2, z2) = p2
	(x3, y3, z3) = p3
	(a1, b1, c1) = (x2 - x1, y2 - y1, z2 - z1)
	(a2, b2, c2) = (x3 - x1, y3 - y1, z3 - z1)
	(a, b, c) = (b1 * c2 - b2 * c1, a2 * c1 - a1 * c2, a1 * b2 - b1 * a2)
	d = -a * x1 - b * y1 - c * z1
	g = GCD([a, b, c, d])
	return (a // g, b // g, c // g, d // g)

def cross(a, b):
	return (a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0])

def intersection_of_two_planes(p1, p2):
	(A1, B1, C1, D1) = p1
	(A2, B2, C2, D2) = p2
	crossprod = cross([A1, B1, C1], [A2, B2, C2])
	if A1 * B2 - A2 * B1 != 0:
		x = ((B1 * D2 - B2 * D1) / (A1 * B2 - A2 * B1), crossprod[0])
		y = ((A2 * D1 - A1 * D2) / (A1 * B2 - A2 * B1), crossprod[1])
		z = (0, crossprod[2])
	elif B1 * C2 - B2 * C1 != 0:
		x = (0, crossprod[0])
		y = ((C1 * D2 - C2 * D1) / (B1 * C2 - B2 * C1), crossprod[1])
		z = ((B2 * D1 - B1 * D2) / (B1 * C2 - B2 * C1), crossprod[2])
	elif A1 * C2 - A2 * C1 != 0:
		x = ((C1 * D2 - C2 * D1) / (A1 * C2 - A2 * C1), crossprod[0])
		y = (0, crossprod[1])
		z = ((A2 * D1 - A1 * D2) / (A1 * C2 - A2 * C1), crossprod[2])
	else:
		return None
	return (x, y, z)

def line_parametric(p1, p2):
	(x1, y1, z1) = p1
	(x2, y2, z2) = p2
	return ((x2, x1 - x2), (y2, y1 - y2), (z2, z1 - z2))

def solve_2_by_2(row1, row2):
	(a1, b1, c1) = row1
	(a2, b2, c2) = row2
	if a1 * b2 - b1 * a2:
		return ((c1 * b2 - b1 * c2) / (a1 * b2 - b1 * a2), (a1 * c2 - c1 * a2) / (a1 * b2 - b1 * a2))
	else:
		return None

def sgn(x):
	return 1 if x > 0 else 0 if x == 0 else -1

def lines_intersection_point(i1, i2):
	(x1, y1, z1) = i1
	(x2, y2, z2) = i2
	try:
		(t1, t2) = solve_2_by_2([x1[1], -x2[1], x2[0] - x1[0]], [y1[1], -y2[1], y2[0] - y1[0]])
		if abs(t1 * z1[1] - t2 * z2[1] - z2[0] + z1[0]) < EPS:
			return ((x1[0] + t1 * x1[1], y1[0] + t1 * y1[1], z1[0] + t1 * z1[1]), t2)
		else:
			return None
	except:
		try:
			(t1, t2) = solve_2_by_2([x1[1], -x2[1], x2[0] - x1[0]], [z1[1], -z2[1], z2[0] - z1[0]])
			if abs(t1 * y1[1] - t2 * y2[1] - y2[0] + y1[0]) < EPS:
				return ((x1[0] + t1 * x1[1], y1[0] + t1 * y1[1], z1[0] + t1 * z1[1]), t2)
			else:
				return None
		except:
			try:
				(t1, t2) = solve_2_by_2([y1[1], -y2[1], y2[0] - y1[0]], [z1[1], -z2[1], z2[0] - z1[0]])
				if abs(t1 * x1[1] - t2 * x2[1] - x2[0] + x1[0]) < EPS:
					return ((x1[0] + t1 * x1[1], y1[0] + t1 * y1[1], z1[0] + t1 * z1[1]), t2)
				else:
					return None
			except:
				return None

def foo(points):
	(down_cnt, up_cnt) = (0, 0)
	first = points[0]
	other = 1 - first
	down = True
	intrusion = True
	for p in points[1:]:
		if p == first:
			intrusion = not intrusion
		else:
			if intrusion:
				if down:
					down_cnt += 1
				else:
					up_cnt += 1
			down = not down
	return down_cnt == up_cnt

def populate(plane, poly, tag):
	res = []
	prev = plane_value(plane, poly[-1])
	prev_serious = plane_value(plane, poly[-2]) if not prev else prev
	p_prev = poly[-1]
	for i in range(len(poly) + 1):
		p = poly[i % len(poly)]
		curr = plane_value(plane, p)
		if sgn(curr) == -sgn(prev_serious):
			intersector = line_parametric(p_prev, p)
			(point, t) = lines_intersection_point(intersector, intersectee)
			res.append((t, tag))
			prev_serious = curr
		if sgn(curr):
			prev_serious = curr
		(prev, p_prev) = (curr, p)
	return res
(x_poly, y_poly) = ([], [])
for _ in range(inp()):
	x_poly.append(inlt())
for _ in range(inp()):
	y_poly.append(inlt())
x_plane = plane(*x_poly[:3])
y_plane = plane(*y_poly[:3])
intersectee = intersection_of_two_planes(x_plane, y_plane)
if intersectee:
	points = sorted(set(populate(y_plane, x_poly, 0) + populate(x_plane, y_poly, 1)))
	points = [i[1] for i in points]
	print('NO' if foo(points) else 'YES')
else:
	print('NO')


def convert_to_float(poly):
	poly_float = []
	for (x, y, z) in poly:
		vertex = (float(x), float(y), float(z))
		poly_float.append(vertex)
	return poly_float

def cross_product(a, b):
	return (a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0])

def dot_product(a, b):
	return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]

def vect_diff(a, b):
	return (a[0] - b[0], a[1] - b[1], a[2] - b[2])

def poly_normal(poly):
	assert len(poly) >= 3
	(x, y, z) = poly[:3]
	u = vect_diff(y, x)
	v = vect_diff(z, y)
	return cross_product(u, v)

def intersect_list(poly, plain_norm, plain_point, proj_dir):
	u = [dot_product(vert, proj_dir) for vert in poly]
	vr = dot_product(plain_point, plain_norm)
	v = [dot_product(vert, plain_norm) for vert in poly]
	u_list = []
	for i in range(len(poly)):
		if (v[i - 1] > vr) != (v[i] > vr):
			ur = ((vr - v[i - 1]) * u[i] + (v[i] - vr) * u[i - 1]) / (v[i] - v[i - 1])
			u_list.append(ur)
	return u_list

def points_to_str(a_points, b_points):
	a_pairs = [('a', val) for val in a_points]
	b_pairs = [('b', val) for val in b_points]
	pairs = sorted(a_pairs + b_pairs, key=lambda pair: pair[1])
	letters = [ch for (ch, _) in pairs]
	return ''.join(letters)

def recognize_str(s):
	toggle = {'a': 'b', 'b': 'a'}
	cross_num = 0
	top = None
	for ch in s:
		if not cross_num:
			cross_num = 1
			top = ch
			continue
		if ch == top:
			cross_num -= 1
		else:
			cross_num += 1
		if cross_num:
			top = toggle[top]
		else:
			top = None
	return not cross_num

def is_well_connected(a, b):
	a = convert_to_float(a)
	b = convert_to_float(b)
	a_norm = poly_normal(a)
	b_norm = poly_normal(b)
	common_dir = cross_product(a_norm, b_norm)
	if not any(common_dir):
		return False
	a_list = intersect_list(a, b_norm, b[0], common_dir)
	b_list = intersect_list(b, a_norm, a[0], common_dir)
	char_str = points_to_str(a_list, b_list)
	return not recognize_str(char_str)

def run_from_console():
	(a_len,) = [int(num) for num in input().split()]
	a = []
	for _ in range(a_len):
		vertex = tuple((int(num) for num in input().split()))
		a.append(vertex)
	(b_len,) = [int(num) for num in input().split()]
	b = []
	for _ in range(b_len):
		vertex = tuple((int(num) for num in input().split()))
		b.append(vertex)
	if is_well_connected(a, b):
		print('YES')
	else:
		print('NO')

def __starting_point():
	run_from_console()
__starting_point()