시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 655 116 73 29.918%

문제

트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르면 개구리에게 키스를 하면 개구리는 아름다운 공주로 변한다고 한다. 일단 개구리를 잡아야 전설이 사실인지 아닌지 확인할 수 있다. 개구리를 잡아보자.

호수는 2차원 평면으로 생각할 수 있고, 식물은 그 평면 위의 점으로 나타낼 수 있다. (x, y)위에 있는 개구리는 아래 네 가지 방향 중 한 방향으로 점프할 수 있다.

  1. 임의의 양의 정수 P에 대해서, (x+P, y+P)로 점프할 수 있다. 이 방향을 A라고 한다.
  2. 임의의 양의 정수 P에 대해서, (x+P, y-P)로 점프할 수 있다. 이 방향을 B라고 한다.
  3. 임의의 양의 정수 P에 대해서, (x-P, y+P)로 점프할 수 있다. 이 방향을 C라고 한다.
  4. 임의의 양의 정수 P에 대해서, (x-P, y-P)로 점프할 수 있다. 이 방향을 D라고 한다.

개구리는 네 방향 중 한 방향을 고른다. 그 다음 그 방향에 있는 가장 가까운 식물로 점프를 한다. 만약, 고른 방향에 식물이 없다면, 개구리는 그 위치에 그대로 있는다. 개구리가 점프를 하고 난 이후에, 원래 있던 식물은 호수로 가라앉게되고 사라진다.

상근이는 식물의 위치와 개구리가 고른 방향을 모두 알고 있다. 상근이는 개구리의 점프가 끝나는 꽃의 좌표를 알아낸 다음, 거기서 개구리를 잡으려고 한다.

개구리의 점프가 끝나는 식물의 위치는 어디일까?

입력

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

둘째 줄에는 개구리가 고른 방향 K개가 주어진다. 이 방향은 'A','B','C','D'로만 이루어져 있다.

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

출력

개구리의 점프가 끝나는 식물의 좌표를 출력한다.

예제 입력 1

7 5
ACDBB
5 6
8 9
4 13
1 10
7 4
10 9
3 7

예제 출력 1

7 4
W3sicHJvYmxlbV9pZCI6IjI5ODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWFkNmNcdWI5YWMgXHVhY2Y1XHVjOGZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQyYjhcdWI3ZWRcdWM3NDQgXHVkMGMwXHVhY2UwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjM1OCBcdWM5MTFcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDczNFx1YzJkZFx1Yzc0NCBcdWNkZThcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDYzOFx1YzIxOFx1YzVkMCBcdWM3YTBcdWMyZGMgXHViNGU0XHViODM4XHViMmU0LiBcdWQ2MzhcdWMyMThcdWM1ZDBcdWIyOTQgXHVhYzFjXHVhZDZjXHViOWFjXHVhYzAwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YWMxY1x1YWQ2Y1x1YjlhY1x1YjI5NCBcdWQ2MzhcdWMyMTggXHVjNzA0XHVjNWQwIFx1YjVhMFx1Yzc4OFx1YjI5NCBcdWMyZGRcdWJiM2MgTlx1YWMxY1x1Yjk3YyBcdWM4MTBcdWQ1MDRcdWQ1NThcdWJhNzRcdWMxMWMgXHViMmU0XHViMmNjXHViMmU0LiBcdWM2MjRcdWI3OThcdWI0MWMgXHVjODA0XHVjMTI0XHVjNWQwIFx1YjUzMFx1Yjk3NFx1YmE3NCBcdWFjMWNcdWFkNmNcdWI5YWNcdWM1ZDBcdWFjOGMgXHVkMGE0XHVjMmE0XHViOTdjIFx1ZDU1OFx1YmE3NCBcdWFjMWNcdWFkNmNcdWI5YWNcdWIyOTQgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YWNmNVx1YzhmY1x1Yjg1YyBcdWJjYzBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3N2NcdWIyZTggXHVhYzFjXHVhZDZjXHViOWFjXHViOTdjIFx1YzdhMVx1YzU0NFx1YzU3YyBcdWM4MDRcdWMxMjRcdWM3NzQgXHVjMGFjXHVjMmU0XHVjNzc4XHVjOWMwIFx1YzU0NFx1YjJjY1x1YzljMCBcdWQ2NTVcdWM3NzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzFjXHVhZDZjXHViOWFjXHViOTdjIFx1YzdhMVx1YzU0NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVkNjM4XHVjMjE4XHViMjk0IDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0XHVjNzNjXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWMyZGRcdWJiM2NcdWM3NDAgXHVhZGY4IFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM3NTggXHVjODEwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiAoeCwgeSlcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWMxY1x1YWQ2Y1x1YjlhY1x1YjI5NCBcdWM1NDRcdWI3OTggXHViMTI0IFx1YWMwMFx1YzljMCBcdWJjMjlcdWQ1YTUgXHVjOTExIFx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjNzg0XHVjNzU4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggUFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsICh4K1AsIHkrUClcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJjMjlcdWQ1YTVcdWM3NDQgQVx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCAoeCtQLCB5LVApXHViODVjIFx1YzgxMFx1ZDUwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViYzI5XHVkNWE1XHVjNzQ0IEJcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3ODRcdWM3NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBQXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgKHgtUCwgeStQKVx1Yjg1YyBcdWM4MTBcdWQ1MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmMyOVx1ZDVhNVx1Yzc0NCBDXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzg0XHVjNzU4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggUFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsICh4LVAsIHktUClcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJjMjlcdWQ1YTVcdWM3NDQgRFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVhYzFjXHVhZDZjXHViOWFjXHViMjk0IFx1YjEyNCBcdWJjMjlcdWQ1YTUgXHVjOTExIFx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVhY2UwXHViOTc4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YWRmOCBcdWJjMjlcdWQ1YTVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjMmRkXHViYjNjXHViODVjIFx1YzgxMFx1ZDUwNFx1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhY2UwXHViOTc4IFx1YmMyOVx1ZDVhNVx1YzVkMCBcdWMyZGRcdWJiM2NcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0LCBcdWFjMWNcdWFkNmNcdWI5YWNcdWIyOTQgXHVhZGY4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWFkZjhcdWIzMDBcdWI4NWMgXHVjNzg4XHViMjk0XHViMmU0LiBcdWFjMWNcdWFkNmNcdWI5YWNcdWFjMDAgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU1OFx1YWNlMCBcdWIwOWMgXHVjNzc0XHVkNmM0XHVjNWQwLCBcdWM2ZDBcdWI3OTggXHVjNzg4XHViMzU4IFx1YzJkZFx1YmIzY1x1Yzc0MCBcdWQ2MzhcdWMyMThcdWI4NWMgXHVhYzAwXHViNzdjXHVjNTQ5XHVhYzhjXHViNDE4XHVhY2UwIFx1YzBhY1x1Yjc3Y1x1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHVhYzFjXHVhZDZjXHViOWFjXHVhYzAwIFx1YWNlMFx1Yjk3OCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYWE4XHViNDUwIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMWNcdWFkNmNcdWI5YWNcdWM3NTggXHVjODEwXHVkNTA0XHVhYzAwIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWFmNDNcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiOCBcdWIyZTRcdWM3NGMsIFx1YWM3MFx1YWUzMFx1YzExYyBcdWFjMWNcdWFkNmNcdWI5YWNcdWI5N2MgXHVjN2ExXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzFjXHVhZDZjXHViOWFjXHVjNzU4IFx1YzgxMFx1ZDUwNFx1YWMwMCBcdWIwNWRcdWIwOThcdWIyOTQgXHVjMmRkXHViYjNjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM1YjRcdWI1MTRcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWM4MTBcdWQ1MDRcdWM3NTggXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIEsgJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMxY1x1YWQ2Y1x1YjlhY1x1YWMwMCBcdWFjZTBcdWI5NzggXHViYzI5XHVkNWE1IEtcdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViYzI5XHVkNWE1XHVjNzQwICYjMzk7QSYjMzk7LCYjMzk7QiYjMzk7LCYjMzk7QyYjMzk7LCYjMzk7RCYjMzk7XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmRkXHViYjNjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBYLCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBYLCBZICZsZTsgMSwwMDAsMDAwLDAwMCkgXHVjYzk4XHVjNzRjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyZGRcdWJiM2NcdWM1ZDAgXHVhYzFjXHVhZDZjXHViOWFjXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMWNcdWFkNmNcdWI5YWNcdWM3NTggXHVjODEwXHVkNTA0XHVhYzAwIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWMyZGRcdWJiM2NcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTgzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUFJJTkNFWkEiLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgcGFya2VkIGhpcyB0cnVjayBuZWFyIHRoZSBsYWtlLiBUaGUgbGFrZSBpcyBpbmhhYml0ZWQgYnkgdGhlIGZyb2cgQmFyaWNhLCB3aG8ganVtcHMgYWNyb3NzIE4gcGxhbnRzIGZsb2F0aW5nIG9uIHRoZSBsYWtlJiMzOTtzIHN1cmZhY2UuIEtub3dpbmcgYSBmYWlyIG51bWJlciBvZiBmb2xrIHRhbGVzLCBMdWthIGtub3dzIHRoYXQgaWYgaGUga2lzc2VzIEJhcmljYSwgc2hlIHdpbGwgdHVybiBpbnRvIGEgYmVhdXRpZnVsIHByaW5jZXNzLiBIb3dldmVyLCBoZSBuZWVkcyB0byBjYXRjaCBoZXIgZmlyc3QhJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzc3VtaW5nIGFuIGFlcmlhbCB2aWV3LCB0aGUgcG9zaXRpb24gb2YgYSBwbGFudCBvbiB0aGUgbGFrZSYjMzk7cyBzdXJmYWNlIGNhbiBiZSBkZWZpbmVkIHdpdGggYSBwYWlyIG9mIGNvb3JkaW5hdGVzLiBGcm9tIHBsYW50ICh4LCB5KSBCYXJpY2EgY2FuIGp1bXA6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VG8gcGxhbnQgKHgrUCwgeStQKSwgZm9yIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIFAuIENhbGwgdGhpcyBkaXJlY3Rpb24gQS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VG8gcGxhbnQgKHgrUCwgeSZtaW51cztQKSwgZm9yIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIFAuIENhbGwgdGhpcyBkaXJlY3Rpb24gQi4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VG8gcGxhbnQgKHgmbWludXM7UCwgeStQKSwgZm9yIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIFAuIENhbGwgdGhpcyBkaXJlY3Rpb24gQy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VG8gcGxhbnQgKHgmbWludXM7UCwgeSZtaW51cztQKSwgZm9yIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIFAuIENhbGwgdGhpcyBkaXJlY3Rpb24gRC4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5CYXJpY2Egc2VsZWN0cyBvbmUgb2YgdGhlIGZvdXIgZGlyZWN0aW9ucyBhbmQganVtcHMgb250byB0aGUgZmlyc3QgcGxhbnQgaW4gdGhlIGNob3NlbiBkaXJlY3Rpb24uIElmIHRoZXJlIGlzIG5vIHBsYW50IGluIHRoZSBzZWxlY3RlZCBkaXJlY3Rpb24sIEJhcmljYSBzdGF5cyB3aGVyZSBzaGUgaXMuIEFmdGVyIEJhcmljYSBqdW1wcywgdGhlIHBsYW50IHNoZSBqdW1wZWQgZnJvbSBzaW5rcyBhbmQgZGlzYXBwZWFycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+S25vd2luZyB0aGUgbG9jYXRpb25zIG9mIHRoZSBwbGFudHMgYW5kIHRoZSBzZXF1ZW5jZSBvZiBkaXJlY3Rpb25zIEJhcmljYSBjaG9vc2VzLCBMdWthIHdhbnRzIHRvIGRldGVybWluZSBjb29yZGluYXRlcyBvZiB0aGUgcGxhbnQgQmFyaWNhIHdpbGwgZW5kIHVwIG9uLiBMdWthIHdpbGwgd2FpdCBmb3IgaGVyIGF0IHRoYXQgcGxhbnQsIGFtYnVzaCBoZXIgYW5kIGtpc3MgaGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBzb2x2ZXMgTHVrYSYjMzk7cyBwcm9ibGVtIGFuZCBoZWxwcyBoaW0gdHVybiBCYXJpY2EgaW50byBhIGJlYXV0aWZ1bCBwcmluY2Vzcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBLICgxICZsZTsgTiwgSyAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHBsYW50cyBhbmQgdGhlIG51bWJlciBvZiBhdHRlbXB0ZWQganVtcC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIEsgbGV0dGVycyBlYWNoIG9mIHdoaWNoIGlzICYjMzk7QSYjMzk7LCAmIzM5O0ImIzM5OywgJiMzOTtDJiMzOTsgb3IgJiMzOTtEJiMzOTsuIFRoZXNlIGxldHRlcnMgcmVwcmVzZW50IGluIG9yZGVyIHRoZSBkaXJlY3Rpb25zIGluIHdoaWNoIEJhcmljYSBhdHRlbXB0cyB0byBqdW1wLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgWCBhbmQgWSAoMCAmbGU7IFggJmxlOyAxIDAwMCAwMDAgMDAwLCAwICZsZTsgWSAmbGU7IDEwMDAwMDAwMDApLCB0aGUgY29vcmRpbmF0ZXMgb2Ygb25lIHBsYW50LiBCYXJpY2EgaXMgaW5pdGlhbGx5IGxvY2F0ZWQgb24gdGhlIGZpcnN0IHBsYW50LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBCYXJpY2EmIzM5O3MgZmluYWwgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==