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) 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