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

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

7 4

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

5 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)