Ngày xửa ngày xưa ở vương quốc ABC có một nàng công chúa Barica xinh đẹp. Vì ghen ghét với sắc đẹp của nàng mụ phù XYZ đã biến nàng thành một con ếch xanh và đầy cô đến sông ở một hồ nước. Vua cha đã ra thông báo nếu ai kêu được công chúa về sẽ gả công chúa cho người đó. Hôm nay, Peter đi đã nhận lời nhà vua đi cứu công chúa. Con ếch xanh trong hồ nước và nó nhay qua ~N~ cái cây trong hồ nước. Để cứu được công chúa Barica, Peter phải hồn vào con ếch, con ếch sẽ biến thành nàng công chúa Barica xinh đẹp. Tuy nhiên, trước tiên anh phải bắt được con ếch đã.

Từ cây ~(x,y)~, con ếch có thể nhảy theo bốn hướng:

• Hướng 'A': tới cây ~(x+P,y+P)~ với ~P~ nguyên dương;

• Hướng 'B': tới cây ~(x+P,y-P)~ với ~P~ nguyên dương;

• Hướng 'C': tới cây ~(x-P,y+P)~ với ~P~ nguyên dương;

• Hướng 'D': tới cây ~(x-P,y-P)~ với ~P~ nguyên dương.

Với mỗi hướng được chọn, con ếch nhảy đến cây gần nhất theo hướng đó. Nếu không có cây nào thì con ếch giữ nguyên vị trí. Sau khi con ếch nhảy khỏi một cây, cây đó sẽ biến mất.

Yêu cầu: Biết vị trí các cây và dãy ~K~ hướng nhảy, hãy xác định vị trí cuối cùng của con ếch.

Input

• Dòng đầu tiên chứa hai số nguyên ~N,K~ ~(1 \le N,K \le 10^5)~, lần lượt là số cây và số lần nhảy;

• Dòng thứ hai chứa một xâu gồm ~K~ ký tự, mỗi ký tự là 'A', 'B', 'C' hoặc 'D', mô tả các hướng nhảy;

• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~X,Y~ ~(0 \le X,Y \le 10^9)~, là tọa độ của một cây. Con ếch bắt đầu tại cây được ghi đầu tiên.

Output

Ghi ra hai số nguyên là tọa độ cuối cùng của con ếch.

Scoring

Sample Input 1

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

Sample Output 1

7 4

Sample Input 2

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

Sample Output 2

5 3