Princeza

Ο Luka πάρκαρε το φορτηγό του κοντά στη λίμνη. Η λίμνη κατοικείται από τον βάτραχο Barica, ο οποίος πηδά κατά μήκος ~N~ φυτών που επιπλέουν στην επιφάνεια της λίμνης. Γνωρίζοντας αρκετά λαϊκά παραμύθια, ο Luka ξέρει ότι αν φιλήσει την Barica, θα γίνει μια όμορφη πριγκίπισσα. Ωστόσο, πρέπει να την πιάσει πρώτα!
Υποθέτοντας μια εναέρια άποψη, η θέση ενός φυτού στην επιφάνεια της λίμνης μπορεί να οριστεί με ένα ζεύγος συντεταγμένων. Από το φυτό ~(x,\;y)~ η Barica μπορεί να πηδήξει:

• στο φυτό ~(x+P,\;y+P)~, για κάθε θετικό ακέραιο αριθμό ~P~. Ονομάστε αυτήν την κατεύθυνση ~A~.
• στο φυτό ~(x+P,\;y-P)~, για οποιονδήποτε θετικό ακέραιο αριθμό ~P~. Ονομάστε αυτήν την κατεύθυνση ~B~.
• στο φυτό ~(x-P,\;y+P)~, για οποιονδήποτε θετικό ακέραιο αριθμό ~P~. Ονομάστε αυτήν την κατεύθυνση ~C~.
• στο φυτό ~(x-P,\;y-P)~, για οποιονδήποτε θετικό ακέραιο αριθμό ~P~. Ονομάστε αυτήν την κατεύθυνση ~D~.

Η Barica επιλέγει μία από τις τέσσερις κατευθύνσεις και πηδά στο πρώτο φυτό προς την επιλεγμένη κατεύθυνση. Εάν δεν υπάρχει φυτό προς την επιλεγμένη κατεύθυνση, η Barica παραμένει εκεί που είναι. Αφού πηδήξει η Barica, το φυτό που πήδηξε από βυθίζεται και εξαφανίζεται.
Γνωρίζοντας τις θέσεις των φυτών και την ακολουθία των κατευθύνσεων που επιλέγει η Barica, ο Luka θέλει να προσδιορίσει τις συντεταγμένες του φυτού στο οποίο θα καταλήξει η Barica. Ο Luka θα την περιμένει σε εκείνο το φυτό, θα της στήσει ενέδρα και θα τη φιλήσει.
Γράψε ένα πρόγραμμα που λύνει το πρόβλημα του Luka και τον βοηθά να μετατρέψει την Barica σε μια όμορφη πριγκίπισσα.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~N~ και ~K\;(1 \le N, K \le 100\,000)~, τον αριθμό των φυτών και τον αριθμό των απόπειρων άλματος.
Η δεύτερη γραμμή περιέχει ~K~ γράμματα, καθένα από τα οποία είναι τα «~A~», «~B~», «~C~» ή «~D~». Αυτά τα γράμματα αντιπροσωπεύουν κατά σειρά τις κατευθύνσεις προς τις οποίες επιχειρεί να πηδήξει η Barica.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς ~X~ και ~Y\;(0 \le X \le 1\,000\,000\,000,\;0 \le Y \le 1\,000\,000\,000)~, τις συντεταγμένες ενός φυτού. Η Barica βρίσκεται αρχικά στο πρώτο φυτό.

Έξοδος

Τυπώστε τις τελικές συντεταγμένες της Barica.

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

input

7 5
ACDBB
5 6
8 9
4 13
1 10
7 4
10 9
3 7

output

7 4

input

6 12
AAAAAABCCCDD
1 1
2 2
3 3
4 4
5 3
6 2

output

5 3