Frog Princess

Time limit1sMemory limit128 MB

Summary
Simulate a frog jumping to the nearest plant along diagonal directions, removing the departed plant each time, over up to 100,000 moves and plants.
Level

Hard8 of 10

Topics
Segment tree, Simulation, Geometry, Sorting
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

  1. Example 1

    Input
    7 5
ACDBB
5 6
8 9
4 13
1 10
7 4
10 9
3 7
    Expected output
    7 4

  2. Example 2

    Input
    6 12
AAAAAABCCCDD
1 1
2 2
3 3
4 4
5 3
6 2
    Expected output
    5 3