Description

Luka parked his truck by the lake.

Barica lives in the lake, and she jumps across $n$ plants floating on the lake surface.

Luka knows many folk tales, and he knows that if he kisses Barica, she will turn into a cute girl. However, he must catch her first.

Each plant’s position on the lake can be described by a pair of coordinates. From the plant at $(x, y)$, Barica can jump with $p$ being any positive integer.

• Direction A: $(x + p, y + p)$.
• Direction B: $(x + p, y - p)$.
• Direction C: $(x - p, y + p)$.
• Direction D: $(x - p, y - p)$.

Barica chooses one of the four directions, then jumps along the chosen direction to the first plant.

If there is no plant in the chosen direction, Barica stays where she is.

After Barica jumps away, the plant she jumped from disappears.

Given the positions of the plants and the sequence of directions chosen by Barica, Luka wants to determine the coordinates of the plant where Barica will end up. Luka will wait for her at that position and kiss her.

Write a program to solve Luka’s problem and help him turn Barica into a beautiful princess.

Input Format

The first line contains two positive integers $n, k$, representing the number of plants and the number of jumps.

The second line contains $k$ letters, A, B, C, or D, representing the directions of her jumps.

The next $n$ lines each contain two integers $x, y$, representing the coordinates of a plant. Barica initially stands on the first plant.

Output Format

The first line contains 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

Hint

Constraints

For $100\%$ of the testdata, $1 \le n, k \le 10 ^ 5$, $0 \le x, y \le 10 ^ 9$.

Notes

• This problem is worth $60$ points.
• This problem enables the O2 optimization switch by default.
• Translated from COCI2007-2008 CONTEST #6 T5 PRINCEZA, translator:
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5