A Romantic Movie Outing

Ο Brian ο σπασίκλας της επιστήμης των υπολογιστών βγαίνει ραντεβού με την κοπέλα του, Anatevka! Η ρομαντική τοποθεσία της επιλογής του είναι ένας κινηματογράφος - αλλά όχι ένας κινηματογράφος IMAX, φυσικά, καθώς και αυτό θα ήταν πολύ ακριβό.

Αυτός ο κινηματογράφος έχει ~10^9~ σειρές των ~1000~ θέσεων η καθεμία, οι οποίες αρχικά είναι κενές. Οι σειρές είναι αριθμημένες από ~1 ... 10^9~ ξεκινώντας από το πλησιέστερο στην οθόνη και οι θέσεις σε κάθε σειρά αριθμούνται από το ~1 ... 1\,000~ από αριστερά προς δεξιά. Το κάθισμα ~c~ στη σειρά ~r~ συμβολίζεται ως κάθισμα (~r, c~). Τα καθίσματα στις σειρές ~1 ... L~ (~1 \le L \le 1\,000~) θεωρείται ότι είναι "κοντά" στην οθόνη, ενώ τα καθίσματα σε παραπάνω σειρές θεωρούνται "μακριά".

Κατά τη διάρκεια των ~T~ (~1 \le T \le 500\,000~) λεπτών πριν από την έναρξη της ταινίας, μια σειρά από γεγονότα συμβαίνουν. Κατά τη διάρκεια του ~i~-οστου λεπτού, είτε μπαίνει ένα άτομο και κάθεται στην άδεια θέση (~R_i, C_i~), το άτομο καθισμένο στην κατειλημμένη θέση (~R_i, C_i~) φεύγει ή η Anatevka προτείνει να καθίσουν εκείνη και ο Brian στις θέσεις (~R_i, C_i~) και (~R -i, C_i + 1~). Το είδος του ~i~-οστου συμβάντος αντιπροσωπεύεται από τον χαρακτήρα ~E_i~, με ~E_i~ = "E" που υποδεικνύει ένα άτομο που εισέρχεται, ~E_i~ = "L" δείχνει ένα άτομο που φεύγει και ~E_i~ = "S" που δείχνει μια πρόταση καθίσματος. Όλες οι θέσεις που συμμετέχουν στα γεγονότα είναι έγκυρες θέσεις εντός του κινηματογράφου, και κάθε κάθισμα που προτείνει η Anatevka θα είναι "κοντά", καθώς πιστεύει ότι είναι τα καλύτερα.

Κάθε φορά που η Anatevka κάνει μια πρόταση, ο Brian πρέπει φυσικά να αναλύσει την ποιότητά της. Αν κάποια από τις δύο θέσεις που προτείνει είναι ήδη κατειλημμένη, θα πρέπει να εξηγήσει ότι η πρότασή της είναι άκυρη με ένα απλό "No". Διαφορετικά, θα ήθελε να υπολογίσει τη συνολική ταλαιπωρία και των δύο θέσεων σε μία τέτοια τοποθέτηση. Η ταλαιπωρία του να κάτσεις στο κάθισμα (~r, c~) είναι ο αριθμός των κατειλημμένων θέσεων στο οπτικό πεδίο (εκτός από τον εαυτό του). Το οπτικό πεδίο του καθίσματος (~r, c~) περιλαμβάνει όλα τα καθίσματα που δεν είναι πιο μακριά από αυτό από τη θέση (~1, c~) κατά απόσταση Μανχάταν (δηλαδή, απόσταση Μανχάταν μεταξύ (~x_1, y_1~) και (~x_2, y_2~) είναι |~x_1 - x_2~| + |~y_1 - y_2~|), όπως φαίνεται παρακάτω (με το "S" να αντιπροσωπεύει μια προτεινόμενη θέση, και ένα "F" που αντιπροσωπεύει ένα κάθισμα εντός του οπτικού του πεδίου):

Αφού πραγματοποιηθούν όλα τα γεγονότα, η ταινία πρόκειται να ξεκινήσει και πρέπει να ληφθεί μια τελική απόφαση για το που θα καθίσουν - και ο Brian θα το χειριστεί αυτό. Συμπεραίνει ότι οι θέσεις που είναι "μακριά" είναι ξεκάθαρα ανώτερες (καθώς προσφέρουν μια ευρύτερη άποψη της οθόνης), και ξέρει ότι ο λόγος να πάει κανείς στον κινηματογράφο είναι για να έχει μια βέλτιστη εμπειρία θέασης, επομένως η επιλογή δύο διπλανών θέσεων σίγουρα δεν είναι υποχρεωτική. Ως εκ τούτου, θα ήθελε να καθορίσει την ελάχιστη συνολική ταλαιπωρία για οποιεσδήποτε δύο "μακριές", μη κατειλημμένες θέσεις στον κινηματογράφο. Σημειώστε ότι, εάν ένα από τα επιλεγμένα καθίσματα βρίσκεται στο οπτικό πεδίο του άλλου, αυτό δεν μετράει για την ταλαιπωρία του - καθορίζεται μόνο από τα άλλα άτομα που κάθονται στον κινηματογράφο.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους, ~L~ (~1 \le L \le 1\,000~) και ~T~ (~1 \le T \le 500\,000~).

Οι επόμενες ~T~ γραμμές καθεμία περιέχουν ένα χαρακτήρα, ~E_i~ (~E_i \in {E, L, S}~) και δύο ακέραιους, ~R_i~ και ~C_i~, για ~i = 1 ... T~ (~1 \le R_i \le 1\,000\,000\,000~, ~1 \le C_i \le 1\,000~).

Βαθμολογία

Για τις περιπτώσεις δοκιμής αξίας 20% των βαθμών, μπορείτε να υποθέσετε ότι ~L \le 100~ και ~T \le 400~.

Για τις περιπτώσεις δοκιμής αξίας 60% των βαθμών, μπορείτε να υποθέσετε ότι ~L \le 500~ και ~T \le 50\,000~.

Έξοδος

Για κάθε μία από τις προτάσεις της Anatevka (δηλαδή, όταν ~E_i = S~ στην είσοδο), εκτυπώστε τη συμβολοσειρά No αν η πρόταση είναι άκυρη, αλλιώς, εκτυπώστε τη συνολική ταλαιπωρία για οποιδήποτε ζεύγων "μακριών", μη κατειλημμένων θέσεων.

Παράδειγμα

input

3 7
E 1 2
E 2 5
S 3 4
E 2 3
L 2 5
S 1 3
S 2 2

output

3
0
No
0

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

Όταν η Anatevka κάνει την πρώτη της πρόταση οι ~3~ μπροστινές σειρές και οι ~5~ πιο αριστερά στήλες του κινηματογράφου φαίνονται όπως παρακάτω (όπου ένα "P" αναπαριστά ένα άτομο και ένα "S" αναπαριστά μία από τις προτεινόμενες θέσεις):

Το άτομο που κάθεται στη θέση (~1, 2~) είναι στο οπτικό πεδίο και των δύο προτεινόμενων θέσεων, ενώ το άτομο που κάθεται στη θέση (~2, 5~) εμποδίζει μόνο τον δεξιό. Έτσι, η συνολική ταλαιπωρία και για τις δύο θέσεις είναι ~1 + 2 = 3~.

Η δεύτερη πρόταση φαίνεται παρακάτω:

Αυτές οι δύο θέσεις δεν εμποδίζονται από κανέναν, οπότε η συνολική τους ταλαιπωρία είναι ~0~. Η τελευταία πρόταση είναι άκυρη, καθώς ένα από τα δύο καθίσματα (το κάθισμα (~2, 3~)) είναι ήδη κατειλημμένη.

Τέλος, ο Brian μπορεί εύκολα να επιλέξει δύο "μακριές" θέσεις με την καθεμία να έχει ταλαιπωρία ~0~, καθώς ο κινηματογράφος έχει ~10^9 - 3~ "μακριές" σειρές με ~1000~ θέσεις η καθεμία και οι περισσότερες είναι μακριά από τους δύο ανθρώπους που κάθονται στον κινηματογράφο μετά το τελευταίο γεγονός. Για παράδειγμα, μπορεί να επιλέξει να πάρει τη θέση (~4, 6~), ενώ προτείνει στην Anatevka να απλαύσει τη θέα από τη θέση (~100, 1\,000~).