Description

Slavko had an unusual dream. On a sunny morning, $N$ white rectangles climbed onto the roof of Slavko’s house one after another and sunbathed there. Each rectangle chose a position on the roof so that its sides were parallel to the edges of the roof. Some rectangles may cover areas where other rectangles are located. For each rectangle, its length and width are $A_i, B_i$, and its distances to the left and bottom edges of the roof are $X_i, Y_i$, respectively.

After sunset, the rectangles climbed down from the roof and slept. The next day, they found that some rectangles had turned yellow, while others remained white. The rectangles that turned yellow were those that were completely exposed to sunlight.

Determine for each rectangle whether it turned yellow.

Input Format

The first line contains a positive integer $N$, indicating the number of rectangles.

The next $N$ lines each contain integers $X_i, Y_i, A_i, B_i$. The input order is the same as the order in which they climbed onto the roof.

Output Format

Output $N$ lines. If the $i$-th rectangle turned yellow, output DA on the $i$-th line; otherwise, output NE on that line.

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

Hint

Explanation for Sample 1

Rectangles $1, 3$ were not completely exposed to sunlight, so they did not turn yellow:

Constraints

For $10\%$ of the testdata, $N \le 10^4$.

For $100\%$ of the testdata, $1 \le N \le 10^5$, $0 \le X_i, Y_i \le 10^9$, $1 \le A_i, B_i \le 10^9$.

Notes

The score setting follows the original COCI problem. Full score is $130$.

Translated from COCI2018-2019 CONTEST #2 T5 Sunčanje.

Translated by ChatGPT 5