Zvijezda

Ο Mirko και ο Slavko περνούν τον ελεύθερο χρόνο τους παίζοντας με πολύγωνα και βλέποντας μια νέα σεζόν του The Biggest Loser. Ο Mirko σχεδίασε πρόσφατα ένα κυρτό πολύγωνο με ζυγό αριθμό κορυφών ~N~. Στη συνέχεια, ο Slavko εξέτασε κάθε ζεύγος αντίθετων πλευρών (δύο πλευρές είναι απέναντι αν υπάρχουν ~\frac{N}{2} - 1~ πλευρές μεταξύ τους), σχεδίασε ευθείες γραμμές που βρίσκονται σε αυτές τις πλευρές και τις χρωμάτισε μαζί με το τμήμα του επιπέδου που βρίσκεται ανάμεσά τους και περιέχει το πολύγωνο . Τελικά, ο Mirko βρήκε ένα σύνολο σημείων ~Q~ και αποφάσισε να προκαλέσει τον Slavko να απαντήσει για κάθε σημείο εάν βρίσκεται στο έγχρωμο ή άχρωμο μέρος του πεδίου.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~T~ που χρησιμοποιείται ως παράμετρος για τη δημιουργία των ερωτημάτων του Mirko. Αυτός ο αριθμός μπορεί να είναι είτε 0 είτε 1. Η δεύτερη γραμμή περιέχει έναν ζυγό ακέραιο ~N~ από την περιγραφή της εργασίας. Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς ~X_i,\;Y_i\;(0 \le |X_i|, |Y_i| \le 10^9)~ που αντιπροσωπεύουν μία από τις κορυφές του πολυγώνου. Μπορείτε να υποθέσετε ότι οι κορυφές δίνονται με αριστερόστροφη σειρά και ότι δεν υπάρχουν τρεις διαδοχικές κορυφές συγγραμμικές.

Η επόμενη γραμμή περιέχει έναν ακέραιο Q από την περιγραφή της εργασίας. Κάθε μία από τις επόμενες γραμμές ~Q~ περιέχει δύο ακέραιους ~A_i,\;B_i\;(0 \le |A_i|, |B_i| \le 2 \cdot 10_{18})~ που χρησιμοποιούνται ως παραμέτρους για τη δημιουργία του σημείου στο i-στό των ερωτημάτων του Mirko.

Έστω το ~X_i~ ίσο με τον αριθμό των σημείων στο πρώτο ~i~ (invlusive συμπεριλαμβανομένου) των ερωτημάτων του Mirko που βρίσκονται στο έγχρωμο μέρος του επιπέδου. Φυσικά, ~X_0 = 0~. Το σημείο του i-οστού ερωτήματος του Mirko θα πρέπει στη συνέχεια να δημιουργηθεί ως:

~P_i = (A_i \bigoplus (T \cdot X^3_{i-1}),\;B_i \bigoplus (T \cdot X^3_{i-1}))~

όπου ~\bigoplus~ ο τελεστής bitwise xor .

Έξοδος

Η i-οστή γραμμή εξόδου θα πρέπει να περιέχει τη λέξη "DA" (ΝΑΙ στα Κροατικά) εάν το σημείο από το i-στό των ερωτημάτων του Mirko βρίσκεται στο έγχρωμο τμήμα του επιπέδου. Διαφορετικά, η i-οστή γραμμή θα πρέπει να περιέχει τη λέξη "NE" (ΟΧΙ στα Κροατία).

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~1 \le N, Q \le 2000, T = 0~
2	30	~1 \le N, Q \le 10^5, T = 0~
3	60	~1 \le N, Q \le 10^5, T = 1~

Παραδείγματα

input

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

output

DA
NE
DA
NE

input

0
6
-1 -1
2 -1
3 3
2 4
1 4
-2 1
6
2 2
3 0
1 -6
2 6
-5 5
5 10

output

DA
DA
NE
NE
NE
NE

Επεξήγηση του 2ου παραδείγματος:

input

1
6
-1 -1
2 -1
3 3
2 4
1 4
-2 1
6
2 2
3 0
1 -6
2 6
-5 5
5 10

output

DA
DA
DA
NE
NE
NE

Επεξήγηση του 3ου παραδείγματος:

Τα χρωματιστά μέρη του επιπέδου είναι τα ίδια όπως στο δεύτερο παράδειγμα και τα σημεία στα ερωτήματα του Mirko είναι: ~(2, 2),\;(2, 1),\;(9, -14),\;(25, 29),\;(-32,30)~ και ~(30, 17)~.