시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 5 5 55.556%

문제

숭이는 지구에 놀러온 외계인에게 조정당하고 있다. 외계인은 숭이를 이용해서 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 놔두고 다시 자기들의 행성으로 떠나려고 한다. 숭이가 있는 곳은 2차원 평면으로 나타낼 수 있고, 클로버는 N개의 점으로 나타나 있다.

숭이의 절친한 친구인 희웅이와 태완이는 숭이를 찾아 다시 정신을 차리게 해주려고 한다. 숭이는 맨 처음에 (0, 0)에 있고, 외계인은 그에게 명령을 M번 전송한다. 각 명령은 네 방향 중 하나이며, 숭이는 그 방향으로 가장 가까운 네잎 클로버가 있는 곳까지 걸어간다.

네잎 클로버의 위치와 외계인이 전송한 명령이 주어졌을 때, 모든 명령을 수행한 뒤에 숭이가 있는 곳의 위치를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 네잎 클로버의 개수 N과 외계인이 전송한 명령의 수 M이 주어진다. (3 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)

다음 N개 줄에는 네잎 클로버의 위치 Xi, Yi가 주어진다. (-100,000 < Xi, Yi < 100,000) 한 위치에 두 개 이상의 네잎 클로버가 있는 경우는 없다.

마지막 줄에는 외계인이 숭이에게 내린 명령이 주어진다. 왼쪽 방향은 L, 오른쪽은 R, 위는 U, 아래는 D로 주어진다. 항상 주어지는 방향에는 네잎 클로버가 있다.

출력

숭이의 마지막 위치를 출력한다.

예제 입력

10 6
0 0
1 1
2 1
0 2
-1 2
-1 3
2 3
2 4
4 3
2 -1
ULURDL

예제 출력

1 1

힌트