#3128. 「COCI 2018.11」Sunčanje

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

译自 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

样例

样例输入 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

样例解释 1

suncanje.jpg

如图所示,第一个和第三个长方形有部分被覆盖了,因此不能去夏威夷。

样例输入 2

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

样例输出 2

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