시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB143635848.739%

문제

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

4 4
1 1
1 0
0 1
0 0
RULD

예제 출력 1

0 0

예제 입력 2

7 5
0 0
0 1
0 -1
1 0
1 -1
3 0
3 -1
DRRUD

예제 출력 2

3 -1

예제 입력 3

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

예제 출력 3

1 1
W3sicHJvYmxlbV9pZCI6IjMwODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxMjRcdWM3OGUgXHVkMDc0XHViODVjXHViYzg0XHViOTdjIFx1Y2MzZVx1YzU0NFx1YzExYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMjJkXHVjNzc0XHViMjk0IFx1YzljMFx1YWQ2Y1x1YzVkMCBcdWIxODBcdWI3ZWNcdWM2MjggXHVjNjc4XHVhY2M0XHVjNzc4XHVjNWQwXHVhYzhjIFx1Yzg3MFx1YzgxNVx1YjJmOVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc0MCBcdWMyMmRcdWM3NzRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjEyNFx1Yzc4ZSBcdWQwNzRcdWI4NWNcdWJjODRcdWI5N2MgXHVjYzNlXHVjNzQwIFx1YjRhNCwgXHVjMjJkXHVjNzc0XHViOTdjIFx1YWRmOCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHViMTk0XHViNDUwXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWM3OTBcdWFlMzBcdWI0ZTRcdWM3NTggXHVkNTg5XHVjMTMxXHVjNzNjXHViODVjIFx1YjVhMFx1YjA5OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzQwIDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWQwNzRcdWI4NWNcdWJjODRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjJkXHVjNzc0XHVjNzU4IFx1YzgwOFx1Y2U1Y1x1ZDU1YyBcdWNlNWNcdWFkNmNcdWM3NzggXHVkNzZjXHVjNmM1XHVjNzc0XHVjNjQwIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YjI5NCBcdWMyMmRcdWM3NzRcdWI5N2MgXHVjYzNlXHVjNTQ0IFx1YjJlNFx1YzJkYyBcdWM4MTVcdWMyZTBcdWM3NDQgXHVjYzI4XHViOWFjXHVhYzhjIFx1ZDU3NFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWI5ZTggXHVjYzk4XHVjNzRjXHVjNWQwICgwLCAwKVx1YzVkMCBcdWM3ODhcdWFjZTAsIFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc0MCBcdWFkZjhcdWM1ZDBcdWFjOGMgXHViYTg1XHViODM5XHVjNzQ0IE1cdWJjODggXHVjODA0XHVjMWExXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViYTg1XHViODM5XHVjNzQwIFx1YjEyNCBcdWJjMjlcdWQ1YTUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YmE3MCwgXHVjMjJkXHVjNzc0XHViMjk0IFx1YWRmOCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWIxMjRcdWM3OGUgXHVkMDc0XHViODVjXHViYzg0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWFlNGNcdWM5YzAgXHVhYzc4XHVjNWI0XHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2M2YmMzNDRiLTZmNTItNGVjNS1iNTg4LTU2ZmUxODEzYmZjMVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzMzcHg7IGhlaWdodDogMzMycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjEyNFx1Yzc4ZSBcdWQwNzRcdWI4NWNcdWJjODRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc3NCBcdWM4MDRcdWMxYTFcdWQ1NWMgXHViYTg1XHViODM5XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YjRhNFx1YzVkMCBcdWMyMmRcdWM3NzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjEyNFx1Yzc4ZSBcdWQwNzRcdWI4NWNcdWJjODRcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWFjZmMgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzc0IFx1YzgwNFx1YzFhMVx1ZDU1YyBcdWJhODVcdWI4MzlcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgTSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxMjRcdWM3OGUgXHVkMDc0XHViODVjXHViYzg0XHVjNzU4IFx1YzcwNFx1Y2U1OCBYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwMCwwMDAgJmx0OyBYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj4gJmx0OyAxMDAsMDAwKSBcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YjEyNFx1Yzc4ZSBcdWQwNzRcdWI4NWNcdWJjODRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzc0IFx1YzIyZFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWIwYjRcdWI5YjAgXHViYTg1XHViODM5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YmMyOVx1ZDVhNVx1Yzc0MCBMLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgUiwgXHVjNzA0XHViMjk0IFUsIFx1YzU0NFx1Yjc5OFx1YjI5NCBEXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM1ZDBcdWIyOTQgXHViMTI0XHVjNzhlIFx1ZDA3NFx1Yjg1Y1x1YmM4NFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMjJkXHVjNzc0XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUUkFUSU5cdTAxMGNJQ0UiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIE1pcmtvIHdhcyBjYXJlbGVzc2x5IHBpY2tpbmcgY2xvdmVycywgaGUgd2FzIHBvc3Nlc2VkIGJ5IGFsaWVucyBhbmQgaGUgd2FzIG5vdyB1bmRlciB0aGVpciBjb250cm9sLiBUaGUgZmllbGQgaXMgYSBDYXJ0ZXNpYW4gY29vcmRpbmF0ZSBzeXN0ZW0gY29udGFpbmluZyBOIHBvaW50cyByZXByZXNlbnRpbmcgY2xvdmVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGlzIHBhcmVudHMgZm91bmQgb3V0IGhlIHdhcyBwb3NzZXNlZCBhbmQgdGhleSBtYW5hZ2VkIHRvIGdldCBpbmZvIG9uIGhvdyBhbGllbnMgY29udHJvbCBoaW0uIFRoZSBhbGllbnMgZmlyc3QgcGxhY2UgaGltIGF0IHBvaW50ICgwLCAwKSwgYW5kIHRoZW4gcGVyZm9ybSBNIHN0ZXBzIHdoZXJlIGluIGVhY2ggc3RlcCB0aGV5IHBpY2sgYSBkaXJlY3Rpb24gKHVwLCBkb3duLCBsZWZ0IG9yIHJpZ2h0KSBhbmQgc2VuZCBoaW0gZnJvbSBoaXMgY3VycmVudCBsb2NhdGlvbiB0byB0aGUgbmV4dCBjbG92ZXIgaW4gdGhhdCBkaXJlY3Rpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYzZiYzM0NGItNmY1Mi00ZWM1LWI1ODgtNTZmZTE4MTNiZmMxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzMzNweDsgaGVpZ2h0OiAzMzJweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+Rm9yIGdpdmVuIGZpZWxkIG9mIGNsb3ZlcnMgYW5kIGRlc2NyaXB0aW9ucyBvZiBNIHN0ZXBzLCBoZWxwIE1pcmtvJiMzOTtzIHBhcmVudHMgZGV0ZXJtaW5lIHdoZXJlIHdpbGwgaGUgZW5kIHVwIGFmdGVyIHRoZSBhbGllbnMgZmluaXNoIHRoZWlyIGNvbnRyb2wuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgzICZsZTsgTiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBNICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgY2xvdmVycyBhbmQgdGhlIG51bWJlciBvZiBzdGVwcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIFg8c3ViPmk8XC9zdWI+IGFuZCBZPHN1Yj5pPFwvc3ViPiAoLTEwMCAwMDAgJmx0OyBYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj4gJmx0OyAxMDAgMDAwKSwgY29vcmRpbmF0ZXMgb2YgdGhlIGktdGggY2xvdmVyLiBUaGVzZSBwb2ludHMgd2lsbCBiZSBtdXR1YWxseSBkaXN0aW5jdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGFzdCBsaW5lIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgTSBjaGFyYWN0ZXMsIHdoZXJlIHRoZSBpLXRoIGNoYXJhY3RlciByZXByZXNlbnRzIHRoZSBkaXJlY3Rpb24gaW4gdGhlIGktdGggc3RlcC4gTCBzdGFuZHMgZm9yIGxlZnQsIFIgZm9yIHJpZ2h0LCBVIGZvciB1cCBhbmQgRCBmb3IgZG93bi4gU3RlcHMgYXJlIGNhcnJpZWQgb3V0IGFzIGZyb20gbGVmdCB0byByaWdodCBhbmQgdGhlcmUgd2lsbCBhbHdheXMgYmUgYSBjbG92ZXIgaW4gYSBnaXZlbiBkaXJlY3Rpb24uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gb25lIGFuZCBvbmx5IGxpbmUgb3V0cHV0IHRoZSBjb29yZGluYXRlcyAoeCwgeSkgd2hpY2ggcmVwcmVzZW50IE1pcmtvJiMzOTtzIGxvY2F0aW9uIGFmdGVyIHRob3NlIE0gc3RlcHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==