네잎 클로버를 찾아서
시간 제한1초메모리 제한128 MB
평면 위에서 시작점이 명령마다 해당 방향의 가장 가까운 네잎클로버로 이동하는 과정을 좌표별로 정렬된 구조를 이용해 효율적으로 시뮬레이션하는 문제입니다.
문제
숭이는 지구에 놀러 온 외계인에게 조종당하고 있다. 외계인은 숭이를 이용해 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 두고 자기들의 행성으로 돌아가려고 한다. 숭이가 움직이는 곳은 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로 주어진다. 각 명령에서 주어진 방향에는 항상 네잎 클로버가 존재한다.
출력
숭이의 마지막 위치를 출력한다.