Princeza

Luka는 호수 근처에 트럭을 주차했다. 호수에는 개구리 Barica가 살고 있는데, 호수 수면에 떠 있는 \(N\)개의 수초 사이를 뛰어다닌다. 민담을 제법 아는 Luka는 Barica에게 입을 맞추면 그녀가 아름다운 공주로 변한다는 것을 알고 있다. 하지만 먼저 그녀를 잡아야 한다!

위에서 내려다볼 때, 호수 수면 위 수초의 위치는 좌표 쌍으로 나타낼 수 있다. 수초 \((x, y)\)에서 Barica는 다음과 같이 뛸 수 있다:

• 양의 정수 \(P\)에 대해 수초 \((x+P, y+P)\)로. 이 방향을 A라고 하자.
• 양의 정수 \(P\)에 대해 수초 \((x+P, y-P)\)로. 이 방향을 B라고 하자.
• 양의 정수 \(P\)에 대해 수초 \((x-P, y+P)\)로. 이 방향을 C라고 하자.
• 양의 정수 \(P\)에 대해 수초 \((x-P, y-P)\)로. 이 방향을 D라고 하자.

Barica는 네 방향 중 하나를 골라 그 방향의 첫 번째 수초로 뛴다. 고른 방향에 수초가 없으면 Barica는 제자리에 머문다. Barica가 뛰고 나면 그녀가 떠난 수초는 가라앉아 사라진다.

수초들의 위치와 Barica가 고르는 방향의 순서를 알고 있을 때, Luka는 Barica가 최종적으로 도착하는 수초의 좌표를 알고 싶어 한다. Luka는 그 수초에서 그녀를 기다렸다가 덮쳐서 입을 맞출 것이다.

Luka의 문제를 풀어 그가 Barica를 아름다운 공주로 만들 수 있도록 돕는 프로그램을 작성하시오.

첫째 줄에 두 정수 \(N\)과 \(K\) (\(1 \le N, K \le 100\,000\))가 주어진다. 수초의 개수와 시도하는 점프의 횟수이다.

둘째 줄에 A, B, C, D 중 하나인 문자 \(K\)개가 주어진다. Barica가 뛰려고 시도하는 방향을 순서대로 나타낸다.

다음 \(N\)개의 줄에는 두 정수 \(X\)와 \(Y\) (\(0 \le X \le 1\,000\,000\,000\), \(0 \le Y \le 1\,000\,000\,000\))가 주어진다. 수초 하나의 좌표이다. Barica는 처음에 첫 번째 수초 위에 있다.

Barica의 최종 좌표를 출력한다.

riseoj 작성

출처 COCI 2007/2008 Contest 6