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.

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

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 \le X \le 1\,000\,000\,000\), \(0 \le Y \le 1\,000\,000\,000\)), the coordinates of one plant. Barica is initially located on the first plant.

Output Barica's final coordinates.

riseoj 작성

출처 COCI 2007/2008 Contest 6