Radio

Στην Κροατία υπάρχουν ~n~ ραδιοφωνικοί σταθμοί. Κάθε σταθμός έχει μια παραχώρηση σε μία από τις n συχνότητες που συμβολίζονται με θετικούς ακέραιους αριθμούς από το 1 έως το ~n~. Οι συχνότητες δεν επιλέχθηκαν ιδανικά, επομένως μερικές φορές εμφανίζεται θόρυβος όταν εκπέμπουν πολλοί σταθμοί ταυτόχρονα. Για να είμαστε πιο ακριβείς, εάν δύο ραδιοφωνικοί σταθμοί, με συχνότητες ~a~ και ~b~ αντίστοιχα, εκπέμπουν ταυτόχρονα, θα εμφανιστεί θόρυβος εάν οι ~a~ και ~b~ δεν είναι σχετικά πρώτοι. Στους ακροατές, φυσικά, δεν αρέσει ο θόρυβος, οπότε όταν τον ακούνε αλλάζουν σταθμό.

Για να λύσετε το πρόβλημα του θορύβου, οι ιδιοκτήτες των ραδιοφωνικών σταθμών σας ζητούν να γράψετε ένα πρόγραμμα που προσομοιώνει τις ενέργειες των ραδιοφωνικών σταθμών. Το πρόγραμμά σας πρέπει να υποστηρίζει δύο τύπους ερωτημάτων:

1. ~S \; x~: Εάν δεν εκπέμπει αυτήν τη στιγμή ο σταθμός με συχνότητα ~x~ αρχίζει να εκπέμπει και εάν ήδη εκπέμπει, σταματά.

2. ~C \; l \; r~: Ελέγξτε εάν υπάρχει ζεύγος ραδιοφωνικών σταθμών των οποίων οι συχνότητες ~a~ και ~b~ είναι στο διάστημα ~[l,\;r]~ και ~gcd(a,\;b) \ne 1~. Εάν υπάρχει τέτοιο ζεύγος, εκτυπώστε DA, διαφορετικά εκτυπώστε NE.

Αρχικά δεν εκπέμπει κανένας σταθμός.

Είσοδος

Η πρώτη γραμμή περιέχει θετικούς ακέραιους αριθμούς ~n~ και ~q\;(1 \le n \le 1\,000\,000,\;1 \le q \le 200\,000)~, τον αριθμό των ραδιοφωνικών σταθμών (και συχνοτήτων) και τον αριθμό των ερωτημάτων, αντίστοιχα.

Η ~i~-οστή των επόμενων γραμμών ~q~ περιέχει μια περιγραφή του ~i~-οστού ερωτήματος. Για ερωτήματα του πρώτου τύπου θα ισχύει ότι ~1 \le x \le n~ και για ερωτήματα του δεύτερου τύπου θα ισχύει ότι ~1 \le l \le r \le n~.

Έξοδος

Εκτυπώστε τις απαντήσεις στα ερωτήματα του δεύτερου τύπου με τη σειρά, σε ξεχωριστές γραμμές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n \le 100,\;1 \le q \le 200~
2	30	Για όλα τα ερωτήματα του δεύτερου τύπου ισχύει ότι ~l = 1~ και ~r = n~.
3	70	Κανένας επιπλέον περιορισμός.

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

input

6 8
S 1
S 2
S 3
C 1 6
S 6
C 1 6
S 2
C 1 6

output

NE
DA
DA

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

Οι σταθμοί που εκπέμπουν κατά την πρώτη ερώτηση τύπου ~C~ είναι οι 1, 2 και 3. Αυτοί οι αριθμοί είναι όλοι σχετικά πρώτοι μεταξύ τους, επομένως δε δημιουργούν θόρυβο. Μόλις ο σταθμός 6 αρχίσει να εκπέμπει, δημιουργεί θόρυβο με τους σταθμούς 2 και 3. Όταν ο σταθμός 2 σταματήσει να εκπέμπει, ο θόρυβος με το σταθμό 3 παραμένει.

input

11 6
S 4
S 10
C 3 11
C 2 7
S 6
C 2 7

output

DA
NE
NE

input

20 7
S 10
S 15
S 3
C 10 15
S 10
C 3 15
C 3 10

output

DA
DA
NE