Frog Princess

A traveler wants to know where a frog will be after it jumps across plants floating on a lake.

Treat the lake as a two-dimensional plane. Each plant is a point (x, y). From its current position (x, y), the frog chooses one of four directions each turn.

• A: toward (x+P, y+P) for a positive integer P
• B: toward (x+P, y-P) for a positive integer P
• C: toward (x-P, y+P) for a positive integer P
• D: toward (x-P, y-P) for a positive integer P

If at least one plant exists in the chosen direction, the frog jumps to the nearest such plant. If none exists, it stays where it is. Only when the frog actually jumps does the plant it just left sink and disappear.

You are given the initial plant and the sequence of chosen directions. Find the coordinates of the plant occupied after all jumps.

The first line contains the number of plants N and the number of jumps K. (1 ≤ N, K ≤ 100,000)

The second line contains a string of length K. Each character is one of A, B, C, and D, and gives the frog's chosen directions in order.

Each of the next N lines contains the coordinates X Y of a plant. (0 ≤ X, Y ≤ 1,000,000,000) The frog starts on the first plant listed.

Print the coordinates X and Y of the plant occupied after all jumps, separated by a space.