시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 29 8 8 66.667%

문제

숭이는 지구에 놀러온 외계인에게 조정당하고 있다. 외계인은 숭이를 이용해서 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 놔두고 다시 자기들의 행성으로 떠나려고 한다. 숭이가 있는 곳은 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로 주어진다. 항상 주어지는 방향에는 네잎 클로버가 있다.

출력

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

예제 입력 1

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 1
W3sicHJvYmxlbV9pZCI6IjMwODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxMjRcdWM3OGUgXHVkMDc0XHViODVjXHViYzg0XHViOTdjIFx1Y2MzZVx1YzU0NFx1YzExYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMjJkXHVjNzc0XHViMjk0IFx1YzljMFx1YWQ2Y1x1YzVkMCBcdWIxODBcdWI3ZWNcdWM2MjggXHVjNjc4XHVhY2M0XHVjNzc4XHVjNWQwXHVhYzhjIFx1Yzg3MFx1YzgxNVx1YjJmOVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc0MCBcdWMyMmRcdWM3NzRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjEyNFx1Yzc4ZSBcdWQwNzRcdWI4NWNcdWJjODRcdWI5N2MgXHVjYzNlXHVjNzQwIFx1YjRhNCwgXHVjMjJkXHVjNzc0XHViOTdjIFx1YWRmOCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHViMTk0XHViNDUwXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWM3OTBcdWFlMzBcdWI0ZTRcdWM3NTggXHVkNTg5XHVjMTMxXHVjNzNjXHViODVjIFx1YjVhMFx1YjA5OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzQwIDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWQwNzRcdWI4NWNcdWJjODRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjJkXHVjNzc0XHVjNzU4IFx1YzgwOFx1Y2U1Y1x1ZDU1YyBcdWNlNWNcdWFkNmNcdWM3NzggXHVkNzZjXHVjNmM1XHVjNzc0XHVjNjQwIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YjI5NCBcdWMyMmRcdWM3NzRcdWI5N2MgXHVjYzNlXHVjNTQ0IFx1YjJlNFx1YzJkYyBcdWM4MTVcdWMyZTBcdWM3NDQgXHVjYzI4XHViOWFjXHVhYzhjIFx1ZDU3NFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWI5ZTggXHVjYzk4XHVjNzRjXHVjNWQwICgwLCAwKVx1YzVkMCBcdWM3ODhcdWFjZTAsIFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc0MCBcdWFkZjhcdWM1ZDBcdWFjOGMgXHViYTg1XHViODM5XHVjNzQ0IE1cdWJjODggXHVjODA0XHVjMWExXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViYTg1XHViODM5XHVjNzQwIFx1YjEyNCBcdWJjMjlcdWQ1YTUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YmE3MCwgXHVjMjJkXHVjNzc0XHViMjk0IFx1YWRmOCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWIxMjRcdWM3OGUgXHVkMDc0XHViODVjXHViYzg0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWFlNGNcdWM5YzAgXHVhYzc4XHVjNWI0XHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Nsb3Zlci5wbmdcIiBzdHlsZT1cImhlaWdodDozMzlweDsgd2lkdGg6MzM5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMTI0XHVjNzhlIFx1ZDA3NFx1Yjg1Y1x1YmM4NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzc0IFx1YzgwNFx1YzFhMVx1ZDU1YyBcdWJhODVcdWI4MzlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHViNGE0XHVjNWQwIFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMTI0XHVjNzhlIFx1ZDA3NFx1Yjg1Y1x1YmM4NFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1YWNmYyBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NzQgXHVjODA0XHVjMWExXHVkNTVjIFx1YmE4NVx1YjgzOVx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjEyNFx1Yzc4ZSBcdWQwNzRcdWI4NWNcdWJjODRcdWM3NTggXHVjNzA0XHVjZTU4IFhpLCBZaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTAwLDAwMCAmbHQ7IFhpLCBZaSAmbHQ7IDEwMCwwMDApIFx1ZDU1YyBcdWM3MDRcdWNlNThcdWM1ZDAgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViMTI0XHVjNzhlIFx1ZDA3NFx1Yjg1Y1x1YmM4NFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NzQgXHVjMjJkXHVjNzc0XHVjNWQwXHVhYzhjIFx1YjBiNFx1YjliMCBcdWJhODVcdWI4MzlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM2N2NcdWNhYmQgXHViYzI5XHVkNWE1XHVjNzQwIEwsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBSLCBcdWM3MDRcdWIyOTQgVSwgXHVjNTQ0XHViNzk4XHViMjk0IERcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmMyOVx1ZDVhNVx1YzVkMFx1YjI5NCBcdWIxMjRcdWM3OGUgXHVkMDc0XHViODVjXHViYzg0XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMyMmRcdWM3NzRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRSQVRJTlx1MDEwY0lDRSIsImRlc2NyaXB0aW9uIjoiPHA+QXMgTWlya28gd2FzIGNhcmVsZXNzbHkgcGlja2luZyBjbG92ZXJzLCBoZSB3YXMgcG9zc2VzZWQgYnkgYWxpZW5zIGFuZCBoZSB3YXMgbm93IHVuZGVyIHRoZWlyIGNvbnRyb2wuIFRoZSBmaWVsZCBpcyBhIENhcnRlc2lhbiBjb29yZGluYXRlIHN5c3RlbSBjb250YWluaW5nIE4gcG9pbnRzIHJlcHJlc2VudGluZyBjbG92ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IaXMgcGFyZW50cyBmb3VuZCBvdXQgaGUgd2FzIHBvc3Nlc2VkIGFuZCB0aGV5IG1hbmFnZWQgdG8gZ2V0IGluZm8gb24gaG93IGFsaWVucyBjb250cm9sIGhpbS4gVGhlIGFsaWVucyBmaXJzdCBwbGFjZSBoaW0gYXQgcG9pbnQgKDAsIDApLCBhbmQgdGhlbiBwZXJmb3JtIE0gc3RlcHMgd2hlcmUgaW4gZWFjaCBzdGVwIHRoZXkgcGljayBhIGRpcmVjdGlvbiAodXAsIGRvd24sIGxlZnQgb3IgcmlnaHQpIGFuZCBzZW5kIGhpbSBmcm9tIGhpcyBjdXJyZW50IGxvY2F0aW9uIHRvIHRoZSBuZXh0IGNsb3ZlciBpbiB0aGF0IGRpcmVjdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbG92ZXIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzM5cHg7IHdpZHRoOjMzOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciBnaXZlbiBmaWVsZCBvZiBjbG92ZXJzIGFuZCBkZXNjcmlwdGlvbnMgb2YgTSBzdGVwcywgaGVscCBNaXJrbyYjMzk7cyBwYXJlbnRzIGRldGVybWluZSB3aGVyZSB3aWxsIGhlIGVuZCB1cCBhZnRlciB0aGUgYWxpZW5zIGZpbmlzaCB0aGVpciBjb250cm9sLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMyAmbGU7IE4gJmxlOyAxMDAgMDAwLCAxICZsZTsgTSAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGNsb3ZlcnMgYW5kIHRoZSBudW1iZXIgb2Ygc3RlcHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBYaSBhbmQgWWkgKC0xMDAgMDAwICZsdDsgWGksIFlpICZsdDsgMTAwIDAwMCksIGNvb3JkaW5hdGVzIG9mIHRoZSBpLXRoIGNsb3Zlci4gVGhlc2UgcG9pbnRzIHdpbGwgYmUgbXV0dWFsbHkgZGlzdGluY3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkxhc3QgbGluZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIE0gY2hhcmFjdGVzLCB3aGVyZSB0aGUgaS10aCBjaGFyYWN0ZXIgcmVwcmVzZW50cyB0aGUgZGlyZWN0aW9uIGluIHRoZSBpLXRoIHN0ZXAuIEwgc3RhbmRzIGZvciBsZWZ0LCBSIGZvciByaWdodCwgVSBmb3IgdXAgYW5kIEQgZm9yIGRvd24uIFN0ZXBzIGFyZSBjYXJyaWVkIG91dCBhcyBmcm9tIGxlZnQgdG8gcmlnaHQgYW5kIHRoZXJlIHdpbGwgYWx3YXlzIGJlIGEgY2xvdmVyIGluIGEgZ2l2ZW4gZGlyZWN0aW9uLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIG9uZSBhbmQgb25seSBsaW5lIG91dHB1dCB0aGUgY29vcmRpbmF0ZXMgKHgsIHkpIHdoaWNoIHJlcHJlc2VudCBNaXJrbyYjMzk7cyBsb2NhdGlvbiBhZnRlciB0aG9zZSBNIHN0ZXBzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==