프로그램 명: coci_princeza
제한시간: 1 초
[문제요약]
루카는 트럭을 호수 근처에 주차했다.
이 호수는 개구리 왕순이가 사는 곳이다. 왕순이는 호수위에 피어 있는 N 개의 식물을 점프 할 수 있다.
여러가지 동화에서 나오다 시피 그가 왕순이 입에다 키스를 하면 왕순이는 아름다운 공주로 변한다.
그보다 먼저 그는 왕순이를 먼저 잡아야 한다.!
4 가지 A,B,C,D 방향은 현재 위치가(x,y) 라면
- To plant (x+P, y+P), for any positive integer P. Call this direction A.
- To plant (x+P, y-P), for any positive integer P. Call this direction B.
- To plant (x-P, y+P), for any positive integer P. Call this direction C.
- To plant (x-P, y-P), for any positive integer P. Call this direction D.
왕순이가 4 방향중 하나를 선택하면 그 방향으로 첫 식물위로 점프를 한다.
선택한 방향으로 식물이 존재하지 않으면 그녀가 있는 곳에 머문다.
왕순이가 점프한 후에 점프한 식물은 물로 가라 앉아서 사라진다.
식물의 위치와 왕순이가 선택한 일련의 방향을 알 때 ,
루카는 왕순이가 최종적으로 머무는 식물의 최종 위치를 알고자 한다.
루카는 그 식물에 기다렸다 잡아서 키스를 하려는 것이다.
루카를 도와 왕순이가 아름다운 공주로 변하는 것을 돕는게 문제이다.
Luka parked his truck near the lake. The lake is inhabited by the frog Barica, who jumps across N
plants floating on the lake's surface. Knowing a fair number of folk tales, Luka knows that if he kisses
Barica, she will turn into a beautiful princess. However, he needs to catch her first!
Assuming an aerial view, the position of a plant on the lake's surface can be defined with a pair of
coordinates. From plant (x, y) Barica can jump:
- To plant (x+P, y+P), for any positive integer P. Call this direction A.
- To plant (x+P, y-P), for any positive integer P. Call this direction B.
- To plant (x-P, y+P), for any positive integer P. Call this direction C.
- To plant (x-P, y-P), for any positive integer P. Call this direction D.
Barica selects one of the four directions and jumps onto the first plant in the chosen direction. If there
is no plant in the selected direction, Barica stays where she is. After Barica jumps, the plant she
jumped from sinks and disappears.
Knowing the locations of the plants and the sequence of directions Barica chooses, Luka wants to
determine coordinates of the plant Barica will end up on. Luka will wait for her at that plant, ambush
her and kiss her.
Write a program that solves Luka's problem and helps him turn Barica into a beautiful princess.
입력
-
The first line contains two integers N and K (1 ≤ N, K ≤ 100 000), the number of plants and the
number of attempted jump.
- The second line contains K letters each of which is 'A', 'B', 'C' or 'D'. These letters represent in order
the directions in which Barica attempts to jump.
Each of the following N lines contains two integers X and Y (0 ≤ X ≤ 1 000 000 000,
0 ≤ Y ≤ 1000000000), the coordinates of one plant. Barica is initially located on the first plant.
출력
Output Barica's final coordinates.
입출력 예
input
7 5
ACDBB
5 6
8 9
4 13
1 10
7 4
10 9
3 7
output
7 4
input
6 12
AAAAAABCCCDD
1 1
2 2
3 3
4 4
5 3
6 2
output
5 3
출처:coci 2007-2008 contest6 5/6
[질/답]
[제출 현황]
[푼 후(0)]