C. Divide Them All
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

After a tough workday Olya and Tolya decided to visit a shooting range. They already heard induction training, got riffles in their hands and are now standing at shooting positions. Across them there is a wall with n targets located on it. Each target can be considered as a figure at the plane and is either a circle or a rectangle. Targets can overlap and intersect in any ways.

Before they start shooting, Olya and Tolya decided to draw a line that will split the plane with all targets in two parts in order to make it possible to identify shots. However, to make it fair they want this line to divide each of the targets in two equal parts. That is, for each circle and each rectangle, the line must divide this figure in two parts of equal area.

Olya and Tolya were arguing hard to come up with this division plan. However, they are not sure that such line even exists and ask you to check whether desired division is possible or not.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of targets. Each of next n lines starts with an integer ti (0 ≤ ti ≤ 1) that define the type of this target. ti = 0 means that this target is a circle and three more integers ri, xi and yi follow (1 ≤ ri ≤ 1000,  - 10 000 ≤ xi, yi ≤ 10 000). They define the radius and coordinates of the circle center respectively. If ti = 1, then this target is a rectangle and it is defined by eight more integers x1, i, y1, i, x2, i, y2, i, x3, i, y3, i, x4, i, y4, i — coordinates of its vertices listed in the order of clockwise or counter-clockwise traversal ( - 10 000 ≤ xj, i, yj, i ≤ 10 000). It is guaranteed that given four points form a rectangle of positive area.

Output

If there exists a line that splits each of the targets in two parts of equal area, print "Yes" in the only line of the output. Otherwise, print "No".