개구리 공주

여행자가 호수 위의 식물들 사이를 뛰어다니는 개구리의 마지막 위치를 알고 싶어 한다.

호수는 2차원 평면이고, 각 식물은 점 (x, y)로 나타낸다. 개구리는 현재 위치 (x, y)에서 매번 네 방향 중 하나를 고른다.

• A: 양의 정수 P에 대해 (x+P, y+P) 방향
• B: 양의 정수 P에 대해 (x+P, y-P) 방향
• C: 양의 정수 P에 대해 (x-P, y+P) 방향
• D: 양의 정수 P에 대해 (x-P, y-P) 방향

고른 방향에 식물이 하나 이상 있으면 그 방향에서 가장 가까운 식물로 점프한다. 그런 식물이 없으면 개구리는 제자리에 머문다. 실제로 점프한 경우에만 방금 떠난 식물은 가라앉아 사라진다.

처음 개구리가 있는 식물과 개구리가 고르는 방향들의 순서가 주어진다. 모든 점프가 끝난 뒤 개구리가 있는 식물의 좌표를 구하라.

첫째 줄에 식물의 수 N과 점프 횟수 K가 주어진다. (1 ≤ N, K ≤ 100,000)

둘째 줄에 길이 K인 문자열이 주어진다. 각 문자는 A, B, C, D 중 하나이며, 순서대로 개구리가 고르는 방향을 뜻한다.

다음 N개의 줄에는 식물의 좌표 X Y가 주어진다. (0 ≤ X, Y ≤ 1,000,000,000) 첫 번째로 주어지는 식물에 개구리가 있다.

모든 점프를 처리한 뒤 개구리가 있는 식물의 좌표 X와 Y를 공백으로 구분해 출력한다.