题目描述

译自 COCI 2018/2019 Contest #2 T5「Sunčanje」

小 Slavko 有一个不寻常的梦想。在一个阳光明媚的早晨，$N$ 个白色的长方形依次爬上了 Slavko 房子上的长方形屋顶。它们准备去夏威夷晒日光浴。它们会找一个位置躺下，边与屋顶的边平行。有可能后来的长方形的身体挡住了之前的长方形的身体部分。每个长方形，已知其长 $A_i$、宽 $B_i$，以及到屋顶左边的距离 $X_i$和到屋顶底部的距离 $Y_i$。

日落之后，长方形们爬下屋顶进入了梦乡，梦到夏威夷的日光将他们的身体晒成了黄色。然而，第二天他们发现了一个问题！只有暴露在阳光下的身体才会被晒成黄色。所以长方形被别的长方形挡住的部分就不会被晒成黄色。

不幸地，那些身体没有完全被筛成黄色的长方形将被强制取消行程。

请你写一个程序来计算哪些长方形可以去夏威夷。

输入格式

第一行一个正整数 $N$，表示长方形的数量。

接下来 $N$ 行每行四个整数 $X_i, Y_i, A_i, B_i$，意义如题目描述所示。这些长方形是按输入顺序躺在屋顶上的。

输出格式

输出 $N$ 行，在第 $i$ 行如果第 $i$ 个长方形能去夏威夷则输出 DA，否则输出 NE。

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

NE
DA
NE
DA
DA

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

NE
NE
DA

数据范围与提示

对于 $10\%$ 的数据，保证 $N \le 10^4$。

对于 $100\%$ 的数据，保证

• $1\le N \le 10^5$
• $0\le X_i, Y_i \le 10^9$
• $1\le A_i, B_i \le 10^9$