Land

Farmer Lasagna bought his dream land, where his cows will live and where he will grow his corn. Cows love to eat corn and will destroy any crop they can reach. So Lasagna plans to build long walls that are high and strong enough that his cows cannot cross them. Lasagna is busy with a performance in Sweden, so he asks you to help him organize his land.

The land is a coordinate plane, and each wall is a line on that plane. Lasagna will send Q queries, and each query is one of two types:

1. Build a wall given by the equation $ax + by = c$, which is the line of all points $(x, y)$ that satisfy it. Lasagna guarantees that $a$ and $b$ are integers from -1 to 1.

2. Given the walls built so far, a cow stands at point $(x_1, y_1)$ and a corn crop is planted at point $(x_2, y_2)$. Can the cow reach $(x_2, y_2)$ and destroy the crop?

Can you help him answer all of his queries?

The first line contains an integer $Q$ ($1 \le Q \le 300000$), the number of queries.

Each of the next $Q$ lines is in one of two formats.

1. "1 a b c", where $a$, $b$, and $c$ are integers with $-1 \le a, b \le 1$, $a \ne 0$ or $b \ne 0$, and $-3 \cdot 10^8 \le c \le 3 \cdot 10^8$. The test data guarantees that when the wall is built, no existing wall coincides with the new wall at every point.

2. "2 x1 y1 x2 y2", where $x_1$, $y_1$, $x_2$, and $y_2$ are integers with $-10^8 \le x_1, y_1, x_2, y_2 \le 10^8$. $(x_1, y_1)$ is the cow's position and $(x_2, y_2)$ is the corn's position. The test data guarantees that at that moment neither point lies on any wall, and the two points are different.

For each query of the second type, print "DA" on its own line if the cow can reach the crop, or "NE" otherwise.

In the first sample, the first line is the x-axis, and it separates points with positive y-coordinates from points with negative y-coordinates. The second line is the y-axis, and together they split the points by quadrant.

The sketch in the third sample shows the lines for all walls and all points that were queried.