Connect the Points

Limits: 2 sec., 512 MiB

There are \(n\) pairs of points with integer coordinates on a two-dimensional plane. The \(i\)-th pair contains points \((x^{(i)}_1, y^{(i)}_1)\) and \((x^{(i)}_2, y^{(i)}_2)\). The \(2n\) points are distinct and each of them lies in the square \([0, n] \times [0, n]\).

Determine whether it is possible to connect every pair of points with a line (not necessarily a straight line) such that the following conditions hold.

• Every drawn line stays strictly inside or on the boundary of the square \([0, n] \times [0, n]\).

• No two lines intersect.

Input

The first line contains an integer \(n\) – the number of pairs.

Each of the next \(n\) lines contains four integers \(x^{(i)}_1, y^{(i)}_1, x^{(i)}_2, y^{(i)}_2\) – the coordinates of the two points of the \(i\)-th pair.

Output

Print YES, if it is possible to connect all pairs without intersections, or NO otherwise.

Constraints

\(1 \le n \le 7\),

\(0 \le x^{(i)}_j, y^{(i)}_j \le n\) for all \(1 \le i \le n, 1 \le j \le 2\),

all \(2n\) points are distinct.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 0 0 3 0 1 1 2 2 0 2 1 2	YES

Input (stdin) сopy	Output (stdout) сopy
2 0 1 2 1 1 0 1 2	NO

Input (stdin) сopy	Output (stdout) сopy
2 0 0 2 2 2 0 1 1	YES

Notes

In the first sample, it is possible to connect the points as shown in the picture above.

In the second sample, it is impossible to connect the points such that the conditions are satisfied.

In the third sample, it is possible to connect the points as shown in the picture above.