Công chúa

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ù thủy 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 cứu được công chúa về sẽ gả công chúa cho người đó. Hôm nay, Peter đã nhận lời nhà vua đi cứu công chúa. Con ếch xanh sống trong hồ nước và nó nhảy qua $N$ cái cây trong hồ nước. Để cứu được công chúa Barica, Peter phải hôn 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 đã.

Giả sử nhìn từ trên không, vị trí của mỗi cây trên mặt hồ được xác định bằng một cặp tọa độ $(x,y)$; các cây có tọa độ đôi một phân biệt. Từ cây $(x,y)$ Barica có thể nhảy:

• Tới cây $(x+P,y+P)$, $P$ nguyên dương. Gọi là hướng A.
• Tới cây $(x+P,y-P)$, $P$ nguyên dương. Gọi là hướng B.
• Tới cây $(x-P,y+P)$, $P$ nguyên dương. Gọi là hướng C.
• Tới cây $(x-P,y-P)$, $P$ nguyên dương. Gọi là hướng D.

Khi đứng ở vị trí $(x,y)$, con ếch chọn một trong bốn hướng và nhảy lên cây đầu tiên theo hướng đã chọn, tức là cây còn tồn tại có $P$ nhỏ nhất. Nếu không có cây nào theo hướng đã chọn, con ếch đứng yên ở đó (lần nhảy này không có tác dụng và cây đang đứng không biến mất). Sau khi con ếch nhảy từ cây ở vị trí $(x,y)$ đi, cây đó sẽ biến mất.

Biết được vị trí của các cây và dãy các hướng mà con ếch đã lựa chọn để nhảy. Peter muốn biết được vị trí cuối cùng của con ếch để đợi sẵn ở đó.

Yêu cầu: Hãy lập trình xác định vị trí cuối cùng của con ếch.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên $N$ và $K$ ($1\le N,K\le {10}^5$), là số cây và số lần nhảy của con ếch.
• Dòng thứ hai ghi một xâu gồm $K$ kí tự, mỗi kí tự là A, B, C hoặc D, thể hiện hướng nhảy của con ếch ở từng lần nhảy theo thứ tự.
• Mỗi dòng trong $N$ dòng tiếp theo 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 nhảy từ cây đầu tiên.

Dữ liệu ra

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

Ràng buộc

• $1\le N,K\le {10}^5$.
• $0\le X,Y\le {10}^9$, các cây có tọa độ đôi một phân biệt.

Subtasks

• Subtask 1 ($30\%$ số điểm, khoảng $40\%$ số test): xâu hướng nhảy chỉ gồm một loại kí tự, tức là con ếch chỉ di chuyển theo hướng A, hoặc chỉ theo hướng B, hoặc chỉ theo hướng C, hoặc chỉ theo hướng D.
• Subtask 2 ($30\%$ số điểm, khoảng $40\%$ số test): tọa độ các cây thỏa mãn $0\le X,Y\le 1000$.
• Subtask 3 ($40\%$ số điểm, khoảng $20\%$ số test): không có ràng buộc gì thêm.

Mỗi subtask được chấm theo nhóm: chỉ được điểm của subtask khi đúng mọi test thuộc subtask đó.

Ví dụ