Snail Path

Ένα σαλιγκάρι κινείται πάνω σε ένα άπειρο πλέγμα που αποτελείται από τετράγωνα ίσου μεγέθους. Μπορεί να κινείται οριζόντια (προς τα ανατολικά και τα δυτικά) ή κατακόρυφα (προς τα βόρεια και τα νότια), αλλά δεν μπορεί να κινείται διαγώνια.

Καθώς το σαλιγκάρι κινείται, αφήνει πίσω του ένα ίχνος βλέννας, με αποτέλεσμα τα τετράγωνα του πλέγματος από τα οποία περνά να γίνονται γλοιώδη.

Για παράδειγμα, αφού το σαλιγκάρι κινηθεί προς τα ανατολικά κατά ~3~ τετράγωνα, τα γλοιώδη τετράγωνα θα είναι ~4~, αυτά που φαίνονται στο αντίστοιχο σχήμα.

Δεδομένων των κινήσεων που πραγματοποιεί το σαλιγκάρι, να υπολογίσετε πόσες φορές το σαλιγκάρι εισέρχεται σε ένα γλοιώδες τετράγωνο.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει έναν θετικό ακέραιο ~M~, που αντιπροσωπεύει τον αριθμό των κινήσεων που πραγματοποιεί το σαλιγκάρι.

Οι επόμενες ~M~ γραμμές θα περιγράφουν τις κινήσεις του σαλιγκαριού, με τη σειρά που πραγματοποιούνται. Κάθε κίνηση αποτελείται από ένα κεφαλαίο γράμμα κατεύθυνσης (~N~, ~E~, ~S~ ή ~W~), ακολουθούμενο από έναν θετικό ακέραιο μικρότερο ή ίσο του ~20~, που αντιπροσωπεύει τον αριθμό των τετραγώνων κατά τα οποία κινείται το σαλιγκάρι προς τη συγκεκριμένη κατεύθυνση.

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί:

Βαθμοί	Επιπλέον Περιορισμοί	Όρια
~4~	Το σαλιγκάρι δεν θα κινηθεί ποτέ βόρεια ή δυτικά από την αρχική του θέση και θα παραμείνει κοντά σε αυτήν.	~M \le 20~
~3~	Το σαλιγκάρι θα παραμείνει κοντά στην αρχική του θέση.	~M \le 20~
~6~	Το σαλιγκάρι μπορεί να απομακρυνθεί αρκετά από την αρχική του θέση.	~M \le 1200~
~2~	Το σαλιγκάρι μπορεί να απομακρυνθεί πάρα πολύ από την αρχική του θέση.	~M \le 200.000~

Έξοδος

Να εκτυπώσετε τον μη αρνητικό ακέραιο ~M~, που αντιπροσωπεύει τον αριθμό των φορών που το σαλιγκάρι εισέρχεται σε ένα γλοιώδες τετράγωνο.

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

input

3
S2
N2
S3

output

4

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

Το σχήμα δείχνει τη διαδρομή του σαλιγκαριού. Κάθε φορά που το σαλιγκάρι εισέρχεται σε ένα γλοιώδες τετράγωνο, τοποθετείται ένας αριθμημένος κύκλος πάνω στη διαδρομή.

Παρατηρήστε ότι το σαλιγκάρι μπορεί να εισέλθει στο ίδιο γλοιώδες τετράγωνο περισσότερες από μία φορές.

input

3
S2
W15
N20

output

0

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

Η διαδρομή του σαλιγκαριού αποτελείται από ~38~ γλοιώδη τετράγωνα. Ωστόσο, το σαλιγκάρι δεν επιστρέφει ποτέ σε ένα τετράγωνο αφού φύγει από αυτό. Επομένως, το σαλιγκάρι δεν εισέρχεται ποτέ σε ένα γλοιώδες τετράγωνο.

Τεχνικές Παρατηρήσεις

Ενδέχεται να λάβετε ένα απρόβλεπτο μήνυμα σφάλματος αν το πρόγραμμά σας χρησιμοποιεί υπερβολικά μεγάλη μνήμη. Οι υποβολές σε Python ~3~ για αυτό το πρόβλημα θα αξιολογούνται χρησιμοποιώντας τον τυπικό διερμηνέα python~3~ (Version ~3~.~10~.~12~) αντί για τον pypy~3~ ~7~.~3~.~9~ (Version ~3~.~8~.~13~).