小 Slavko 做了一个不寻常的梦。在一个阳光明媚的早晨，$N$ 个白色的矩形一个接一个地爬上了 Slavko 家的矩形屋顶。它们正准备去夏威夷进行一次异国旅行——日光浴。每个矩形都在屋顶上选择了一个位置，并以其边与屋顶边缘平行的方式躺下。有些矩形可能会重叠在先前已经躺在 Slavko 屋顶上的其他矩形的一部分之上。对于每个矩形，已知其长度 $A_i$、高度 $B_i$ 以及分别到屋顶左边缘和底边缘的距离 $X_i$ 和 $Y_i$。

日落后，矩形们爬下屋顶去睡觉，梦见美丽的夏威夷海滩，以及它们因阳光照射而晒成黄色的身体。然而，第二天早上它们发现了一个问题！只有直接暴露在阳光下的矩形部分才变成了黄色。换句话说，如果一个矩形的某些部分被其他矩形遮挡，那么这些部分就不会从白色变成黄色。

遗憾的是，没有完全变色的矩形被迫取消了这次旅行。

编写一个程序，确定每个矩形是否能去夏威夷。

输入格式

第一行包含一个正整数 $N$（$1 \le N \le 100\,000$），表示矩形的数量。

接下来的 $N$ 行，每行包含四个整数 $X_i, Y_i$（$0 \le X_i, Y_i \le 10^9$），$A_i$ 和 $B_i$（$1 \le A_i, B_i \le 10^9$），按照它们爬上并躺在屋顶上的顺序描述这些矩形。$X_i$ 表示到屋顶左边缘的距离，$Y_i$ 表示到屋顶底边缘的距离，$A_i$ 表示第 $i$ 个矩形的长度，$B_i$ 表示第 $i$ 个矩形的高度。

输出格式

输出 $N$ 行。在第 $i$ 行中，如果第 $i$ 个矩形可以去夏威夷，则输出 DA（克罗地亚语中的“是”），否则输出 NE（克罗地亚语中的“否”）。

子任务

在占总分 $10\%$ 的测试数据中，满足 $N \le 10\,000$。

样例

输入样例 1

5
1 1 4 2
6 1 1 1
2 2 2 3
3 4 3 2
4 0 1 2

输出样例 1

NE
DA
NE
DA
DA

输入样例 2

3
3 3 1 1
2 2 3 3
1 1 5 5

输出样例 2

NE
NE
DA

说明

样例 1 解释：

第一个和第三个矩形没有完全暴露在阳光下，这意味着它们不会完全变色，因此无法去夏威夷。其他矩形则完全暴露在阳光下。