COCI '18 Contest 2 #5 Sunčanje

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 4.0s
Memory limit: 256M

Problem type

Little Slavko dreamed of an unusual dream. One sunny morning, N white rectangles climbed one by one on the rectangular roof of Slavko's house. They were preparing for an exotic trip to Hawaii - sunbathing. Each rectangle chose a place on the roof and lay in such a way that its sides were parallel to the edges of the roof. It is possible that some rectangles overlapped parts of other rectangles that have previously lain down on Slavko's roof. For each rectangle its length A_i, height B_i and distances from the left and bottom edges of the roof, X_i and Y_i, respectively, are known.

After sunset, rectangles climbed down the roof and went to sleep dreaming of beautiful Hawaii beaches and their bodies tanned to yellow due to the sun exposure. However, the next morning they spotted a problem! Only parts of rectangles that had been directly exposed to the sun became yellow. In other words, if parts of a rectangle were covered by some other rectangle, then those parts didn't change colour from white to yellow.

Sadly, rectangles that did not change the colour entirely were forced to cancel the trip. Write a program that will determine for each rectangle if it is going to Hawaii or not.

Input

The first line contains a positive integer N (1 \le N \le 100\,000), number of rectangles. Each of the next N lines contains four integers X_i, Y_i (0 \le X_i, Y_i \le 10^9), A_i and B_i (1 \le A_i, B_i \le 10^9), describing rectangles in the order they were climbing and lying down on the roof. X_i represents distance from the left edge of the roof, Y_i the distance from the bottom edge of the roof, A_i the length and B_i the height of the i^{th} rectangle.

Output

You have to print N lines. In i^{th} line print DA (Croatian for yes, without quotation marks) if i^{th} rectangle will go to Hawaii, otherwise print NE (Croatian for no).

Scoring

In test cases worth 10% of total points, it will hold that N \le 10\,000.

Sample Input 1

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

Sample Output 1

NE
DA
NE
DA
DA

Explanation for Sample Output 1

The first and the third rectangle are not entirely exposed to the sun, meaning they won't change colour entirely and won't go to Hawaii. Other rectangles are exposed to the sun entirely.

Sample Input 2

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

Sample Output 2

NE
NE
DA

Comments

There are no comments at the moment.