Problem O
Princeza

Luka parked his truck near the lake. The lake is inhabited by the frog Barica, who jumps acrossplants 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 paircoordinates. 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 wantsdetermine 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 \leq N, K \leq 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 \leq X \leq 1\, 000\, 000\, 000, 0 \leq Y \leq 1\, 000\, 000\, 000$), the coordinates of one plant. Barica is initially located on the first plant.

Output

Output Barica’s final coordinates.

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