Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Hide-and-Seek

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVictor and Peter are playing hide-and-seek. Peter has hidden, and Victor is to find him. In the room where they are playing, there is only one non-transparent wall and one double-sided mirror. Victor and Peter are points with coordinates (*x*_{v}, *y*_{v}) and (*x*_{p}, *y*_{p}) respectively. The wall is a segment joining points with coordinates (*x*_{w, 1}, *y*_{w, 1}) and (*x*_{w, 2}, *y*_{w, 2}), the mirror — a segment joining points (*x*_{m, 1}, *y*_{m, 1}) and (*x*_{m, 2}, *y*_{m, 2}).

If an obstacle has a common point with a line of vision, it's considered, that the boys can't see each other with this line of vision. If the mirror has a common point with the line of vision, it's considered, that the boys can see each other in the mirror, i.e. reflection takes place. The reflection process is governed by laws of physics — the angle of incidence is equal to the angle of reflection. The incident ray is in the same half-plane as the reflected ray, relative to the mirror. I.e. to see each other Victor and Peter should be to the same side of the line, containing the mirror (see example 1). If the line of vision is parallel to the mirror, reflection doesn't take place, and the mirror isn't regarded as an obstacle (see example 4).

Victor got interested if he can see Peter, while standing at the same spot. Help him solve this problem.

Input

The first line contains two numbers *x*_{v} and *y*_{v} — coordinates of Victor.

The second line contains two numbers *x*_{p} and *y*_{p} — coordinates of Peter.

The third line contains 4 numbers *x*_{w, 1}, *y*_{w, 1}, *x*_{w, 2}, *y*_{w, 2} — coordinates of the wall.

The forth line contains 4 numbers *x*_{m, 1}, *y*_{m, 1}, *x*_{m, 2}, *y*_{m, 2} — coordinates of the mirror.

All the coordinates are integer numbers, and don't exceed 10^{4} in absolute value. It's guaranteed, that the segments don't have common points, Victor and Peter are not on any of the segments, coordinates of Victor and Peter aren't the same, the segments don't degenerate into points.

Output

Output YES, if Victor can see Peter without leaving the initial spot. Otherwise output NO.

Examples

Input

-1 3

1 3

0 2 0 4

0 0 0 1

Output

NO

Input

0 0

1 1

0 1 1 0

-100 -100 -101 -101

Output

NO

Input

0 0

1 1

0 1 1 0

-1 1 1 3

Output

YES

Input

0 0

10 0

100 100 101 101

1 0 3 0

Output

YES

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/24/2019 13:13:33 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|