### COCI 2007/2008, Contest #6

## Task PRINCEZA

Luka parked his truck near the lake. The lake is inhabited by the frog Barica, who jumps across N plants floating on the lake's surface. Knowing a fair number of folk tales, Luka knows that if he kisses Barica, she will turn into a beautiful princess. However, he needs to catch her first!

Assuming an aerial view, the position of a plant on the lake's surface can be defined with a pair of coordinates. From plant (x, y) Barica can jump:

- To plant (x+P, y+P), for any positive integer P. Call this direction A.
- To plant (x+P, y−P), for any positive integer P. Call this direction B.
- To plant (x−P, y+P), for any positive integer P. Call this direction C.
- To plant (x−P, y−P), for any positive integer P. Call this direction D.

Barica selects one of the four directions and jumps onto the first plant in the chosen direction. If there
is no plant in the selected direction, Barica stays where she is. After Barica jumps, **the plant she
jumped from sinks** and disappears.

Knowing the locations of the plants and the sequence of directions Barica chooses, Luka wants to determine coordinates of the plant Barica will end up on. Luka will wait for her at that plant, ambush her and kiss her.

Write a program that solves Luka's problem and helps him turn Barica into a beautiful princess.

### Input

The first line contains two integers N and K (1 ≤ N, K ≤ 100 000), the number of plants and the number of attempted jump.

The second line contains K letters each of which is 'A', 'B', 'C' or 'D'. These letters represent in order the directions in which Barica attempts to jump.

Each of the following N lines contains two integers X and Y (0 ≤ X ≤ 1 000 000 000, 0 ≤ Y ≤ 1 000 000 000), the coordinates of one plant. Barica is initially located on the first plant.

### Output

Output Barica's final coordinates.

### Examples

## Input7 5 ACDBB 5 6 8 9 4 13 1 10 7 4 10 9 3 7 ## Output7 4 |
## Input6 12 AAAAAABCCCDD 1 1 2 2 3 3 4 4 5 3 6 2 ## Output5 3 |

All Submissions

Best Solutions

**Point Value:** 15

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Aug 13, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...