The biannual THUPC is coming again. As veteran participants who have attended countless editions, Xiao C and Xiao Z naturally want to join in the fun. However, being "old folks" now, participating is out of the question. But they have developed aesthetic fatigue toward the THUPC logo, which hasn't changed for years. To better attract people to sign up, they plan to redraw a flashier one.

Laughable, how could you expect two geeky programmers to have any artistic talent?

Knowing this task is beyond their capabilities, they decided to write an artificial idiot to help them draw the logo!

After tireless efforts, their artificial idiot finally runs, but they soon discover that this artificial idiot has even less artistic talent than they do—it only knows how to draw horizontal and vertical line segments on a plane to form the letters "THUPC"!

However, since the program is already written, they might as well use it. After an in-depth study of this characteristic, Xiao C and Xiao Z established the following rules:

For each horizontal line segment, let its horizontal interval be $[l_i, r_i]$ and its vertical coordinate be $y_i$. For each vertical line segment, let its vertical interval be $[d_i, u_i]$ and its horizontal coordinate be $x_i$. All the above values are integers, satisfying $r_i > l_i$ and $u_i > d_i$.

The "THUPC" lettering should be composed of $15$ line segments, numbered $1 \sim 15$. For each letter, the rules are as follows:

The letter "T" consists of horizontal segment $1$ and vertical segment $2$, satisfying $d_2 < y_1 = u_2$ and $l_1 < x_2 < r_1$.

The letter "H" consists of vertical segment $3$, horizontal segment $4$, and vertical segment $5$, satisfying $d_3 = d_5 < y_4 < u_3 = u_5$ and $x_3 = l_4 < r_4 = x_5$.

The letter "U" consists of vertical segment $6$, horizontal segment $7$, and vertical segment $8$, satisfying $d_6 = d_8 = y_7 < u_6 = u_8$ and $x_6 = l_7 < r_7 = x_8$.

The letter "P" consists of vertical segment $9$, horizontal segment $10$, horizontal segment $11$, and vertical segment $12$, satisfying $d_9 < y_{11} = d_{12} < u_9 = y_{10} = u_{12}$ and $x_9 = l_{10} = l_{11} < r_{10} = r_{11} = x_{12}$.

The letter "C" consists of vertical segment $13$, horizontal segment $14$, and horizontal segment $15$, satisfying $d_{13} = y_{15} < u_{13} = y_{14}$ and $x_{13} = l_{14} = l_{15} < r_{14} = r_{15}$.

The $5$ generated letters can be placed anywhere on the plane without needing to be arranged from left to right, but any two line segments belonging to different letters must not intersect.

Note that the order of line segments provided by the artificial idiot may not follow the numbering above; furthermore, the provided segments may have segments of the same orientation that are connected end-to-end, overlapping, or contained within one another, in which case they should be treated as a single continuous line segment.

Only if the generated line segments, after connecting and sorting, conform to the above specifications is the logo considered correctly generated; otherwise, if there are extra segments, missing segments, or coordinates that do not meet the requirements, it is considered incorrect.

Finally, Xiao C and Xiao Z want to write a program to check whether each output from the artificial idiot meets the above specifications, but after staying up for three consecutive nights, they are too exhausted to move, so they have asked you for help.

Input

The first line contains a positive integer $n$, representing the number of line segments, where $1 \leq n \leq 10^5$.

The next $n$ lines each start with an integer $op_i$, which is either $0$ or $1$: if $op_i = 0$, it indicates that the $i$-th segment is a horizontal segment, followed by three integers $l_i, r_i, y_i$ describing the segment, with $l_i < r_i$ guaranteed; if $op_i = 1$, it indicates that the $i$-th segment is a vertical segment, followed by three integers $d_i, u_i, x_i$ describing the segment, with $d_i < u_i$ guaranteed.

All coordinates are guaranteed to be in the range $[-10^9, 10^9]$.

Output

If the output conforms to the specifications, output Yes, otherwise output No.

Examples

Input 1

17
1 0 5 2
0 0 3 5
0 3 4 5
1 2 7 7
1 2 7 10
0 7 10 4
0 11 13 1
1 1 7 11
1 1 7 13
1 0 6 15
0 15 16 5
0 15 16 6
1 5 6 16
1 3 6 18
1 4 7 18
0 18 21 3
0 18 21 7

Output 1

Yes

Note 1

In this sample, the horizontal segment of the letter "T" and the vertical segment of the letter "C" are each composed of two segments joined together.