## Ibrohim and his computer

Statement

Cowboy Beblop is a funny little boy who likes to sit at a computer. From somewhere he got two elastic hoops in the form of two-dimensional polygons, not necessarily convex. Since there is no gravity on his spaceship, the hoops calmly hang in the air (in three-dimensional space). Since the hoops are very elastic, Beblop can stretch them, rotate, move or shorten their ribs as much as they want.
For both hoops, you are given the number of vertices and the coordinates of each vertex, determined by the three numbers x, y, and z. The vertices are given in the traversal order: vertex 1 is connected to vertex 2, vertex 2 is connected to vertex 3, and so on, the last vertex is again connected to the first. Two hoops are considered geared if it is impossible to part them to an infinitely large distance only by changing the lengths of the edges and moving them, but not crossing along either the segments or the vertices - just like two chains. Initially, the edges of the polygons do not intersect and do not touch.
For simplicity, we say that two polygons are strongly geared if the edges of one of the polygons intersect the area of the other in two different directions (from top to bottom and from bottom to top in the plane defined by this polygon) a different number of times.
Cowboy Beblop adores his hoops and would like to know if they are tightly geared or not. Since he is busy playing with his dog, he asks you to determine the answer.

Input description

The first line of the input contains an integer n (3 ≤ n ≤ 100 000) - the number of sides in the first polygon. Each of the next n lines contains three integers x, y and z (- 1 000 000 ≤ x, y, z ≤ 1 000 000) - the coordinates of the vertices in the traversal order. The next line contains the number m (3 ≤ m ≤ 100,000) - the number of vertices in the second rectangle, followed by m lines describing the vertices in the same format as the first rectangle.
It is guaranteed that both rectangles do not contain self-intersections and that the corresponding polygons do not intersect and do not touch. It is additionally guaranteed that no three consecutive vertices of the same polygon lie on one straight line.

Output description

Print "YES" or "NO", depending on whether the two polygons are strongly geared or not.

Constraints

Game modes

Fastest

Test cases

Test 1 Test

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

Test 2 Validator

Input

4
4 -2 0
4 3 0
-3 3 0
-3 -2 0
4
6 -2 0
3 2 2
-3 7 0
3 4 6

Output

NO

Test 3 Test

Input

4
-10 5 0
25 18 0
23 8 0
-9 0 0
5
7 12 -5
7 0 -10
7 3 8
7 10 7
7 6 0

Output

YES

Test 4 Validator

Input

8
0 1000 0
436 1013 0
500 500 0
1000 500 0
1000 1000 0
1401 1000 0
1500 0 0
0 0 0
8
-200 1000 400
150 1000 400
125 250 -500
850 250 -500
750 1000 400
1200 1000 400
1250 0 -800
-250 0 -800

Output

YES

Test 5 Test

Input

9
2564 865 0
573 1115 0
-600 1000 0
100 600 0
949 665 0
2341 -2375 0
3879 -561 0
2200 -600 0
2543 -250 0
10
2900 -1000 0
280 60 900
1990 -480 0
1710 -320 0
830 450 -550
660 280 0
270 260 500
345 460 0
-520 1440 -1000
1300 400 -1000

Output

NO

Test 6 Validator

Input

16
0 1000 0
436 1013 0
500 500 0
1000 500 0
1000 1000 0
1401 1028 0
1434 461 0
2087 442 0
2066 1040 0
2492 1031 0
2541 449 0
3069 451 0
3050 1071 0
3702 1071 0
3754 0 0
0 0 0
16
-243 700 394
109 700 365
129 700 -366
763 700 -366
725 700 397
1131 700 409
1173 700 -339
1910 700 -405
1834 700 414
2254 700 439
2323 700 -425
2847 700 -380
2849 700 477
3418 700 470
3537 700 -1057
-294 700 -777

Output

YES

Test 7 Test

Input

100000
0 0 0
0 10 0
2 10 0
2 5 0
4 5 0
4 10 0
6 10 0
6 5 0
8 5 0
8 10 0
10 10 0
10 5 0
12 5 0
12 10 0
14 10 0
14 5 0
16 5 0
16 10 0
18 10 0
18 5 0
20 5 0
20 10 0
22 10 0
22 5 0
24 5 0
24 10 0
26 10 0
26 5 0
28 5 0
28 10 0
30 10 0
30 5 0
32 5 0
32 10 0
34 10 0
34 5 0
36 5 0
36 10 0
38 10 0
38 5 0
40 5 0
40 10 0
42 10 0
42 5 0
44 5 0
44 10 0
46 10 0
46 5 0
48 5 0
48 10 0
50 10 0
50 5 0
52 5 0
52 10 0
54 10 0
54 5 0
56 5 0
56 10 0
58 10 0
58 5 0
60 ...

Output

NO

Test 8 Validator

Input

200
-16171 -15493 -453
-17103 -17040 -453
-8369 -9081 -453
-16694 -18696 -453
-16214 -19041 -453
-14474 -18419 -453
-12692 -16768 -453
-14762 -21403 -453
-10091 -15370 -453
-13204 -22115 -453
-16685 -29505 -453
-15565 -30439 -453
-12635 -27500 -453
-7951 -18704 -453
-10362 -26787 -453
-6552 -18810 -453
-7955 -25971 -453
-6101 -22180 -453
-4604 -17767 -453
-5712 -24347 -453
-4877 -22947 -453
-3268 -19295 -453
-3918 -26142 -453
-2369 -17180 -453
-2685 -28626 -453
-1236 -18311 -453
...

Output

NO

Solution language

Solution

Stub generator input

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants