Cars on Ice

Η φύλαξη μιας τράπεζας τη νύχτα των Χριστουγέννων μπορεί να γίνει πολύ βαρετή. Γι' αυτό ο Barry αποφάσισε να πάει να κάνει πατινάζ στο πάρκινγκ για λίγο. Ωστόσο, ο χώρος στάθμευσης δεν είναι άδειος καθώς οι άλλοι φρουροί έχουν τα αυτοκίνητά τους παρκαρισμένα εκεί. Έτσι ο Barry αποφασίζει να σπρώξει τα αυτοκίνητά τους έξω από το πάρκινγκ. Παρατηρεί ότι τα αυτοκίνητά τους είναι σταθμευμένα με βόρειο, νότο, ανατολικό ή δυτικό προσανατολισμό. Αφού το πάρκινγκ είναι παγωμένο, σπρώχνοντας ένα αυτοκίνητο θα το κάνει να γλιστρήσει μέχρι να βγει από το πάρκινγκ ή να χτυπήσει άλλο αυτοκίνητο. Τα αυτοκίνητα μπορούν να σπρώχνονται μόνο προς την κατεύθυνση που είναι στραμμένα. Μη θέλοντας να τρακάρει τα αυτοκίνητα, ο Barry επιστρατεύει τη βοήθειά σας για να μάθει με ποιά σειρά πρέπει να σπρώξει τα αυτοκίνητα για να καθαρίσει το πάρκινγκ.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ και ~M~ (~1 \le N, M \le 2\,000~) που αντιπροσωπεύουν τον αριθμό από σειρές και στήλες του πάρκινγκ. Οι επόμενες ~N~ γραμμές καθεμία περιέχουν ~M~ χαρακτήρες που αντιπροσωπεύουν το πάρκινγκ, όπου '.' αντιπροσωπεύει μία άδεια θέση, ενώ 'N', 'S', 'E' και 'W' καθένα αντιπροσωπεύει ένα αυτοκίνητο (με κατεύθυνση Βόρεια, Νότια, Ανατολική ή Δυτική αντίστοιχα).

Βαθμολογία

Για τουλάχιστον 70% της βαθμολογίας, ~N \le 100~ και ~M \le 100~.

Έξοδος

Εκτυπώστε τη σειρά με την οποία τα αυτοκίνητα πρέπει να σπρωχτούν έτσι ώστε να καθαριστεί το πάρκινγκ χωρίς συγκρούσεις. Εκτυπώστε κάθε αυτοκίνητο με τη μορφή (~r, c~), όπου ~r~ και ~c~ είναι οι συντεταγμένες του αυτοκινήτου στο πάρκινγκ (όπου (~0, 0~) είναι το πιο πάνω αριστερά σημείο και (~N - 1, M - 1~) είναι το πιο κάτω δεξιά σημείο).

Μπορείτε να υποθέσετε ότι πάντα θα υπάρχει τουλάχιστον μία έγκυρη λύση.

Αν υπάρχουν πολλαπλές πιθανές λύσεις, εκτυπώστε οποιαδήπουε έγκυρη λύση.

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

input

5 5
. . . . .
. E . S .
. . . . .
. . . . .
. N . E .

output

(4, 3)
(1, 3)
(1, 1)
(4, 1)

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

Το μόνο αμάξι που αρχικά δεν είναι μπλοκαρισμένο από ένα άλλο αμάξι είναι αυτό στο σημείο (~4~, ~3~). Αφού σπρωχτεί έξω στα δεξιά του πάρκινγκ, τότε το αμάξι από πάνω του (στο (~1, 3~)) μπορεί να σπρωχτεί και μετά εκείνο στη θέση (~1, 1~) και τέλος το αμάξι στη θέση (~4, 1~), καθαρίζοντας έτσι το πάρκινγκ.

input

4 3
. . .
. N .
. S .
. . .

output

(1, 1)
(2, 1)

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

Οποιοδήποτε από τα δύο αυτοκίνητα θα μπορούσε να σπρωχτεί πρώτο για να καθαρίσει το πάρκινγκ, οπότε αυτή η έξοδος είναι αποδεκτή (όπως θα ήταν και η έξοδος με τις εκτυπωμένες γραμμές να έχουν την αντίθετη σειρά).