Connect the Points#13018

Connect the Points

2 seconds
512 megabytes
Hard

There are pairs of points with integer coordinates on a two-dimensional plane. The -th pair contains points (x^{(i)}_1, y^{(i)}_1) and (x^{(i)}_2, y^{(i)}_2). The 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.

Input

The first line contains an integer – the number of pairs.

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

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 points are distinct.

Output

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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.