D. A Bug That's Not a Pill Bug
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A bug that looks like a pill bug is walking on a plane. A Cartesian coordinate system is defined on the plane, in which its $$$x$$$-axis is directed from west to east, while its $$$y$$$-axis is directed from south to north.

The bug is initially at a lattice point (a point where both the $$$x$$$- and $$$y$$$-)coordinates are integers), facing the positive direction of $$$x$$$. Obstacles are placed at some of the lattice points on the plane. The bug continues to move according to the following rules, avoiding obstacles.

  • The bug attempts to move from its current position to the adjacent lattice point in the direction it is currently facing.
  • If that adjacent lattice point has no obstacles, the bug moves there without changing its direction.
  • If that adjacent lattice point has an obstacle, the bug turns 90 degrees to the left, without changing its position.

The initial position of the bug, the locations of the obstacles, and a moving distance are given. You are requested to find the position of the bug after it has moved exactly the given distance.

Some of the datasets in Sample Input are illustrated below. The points marked with an "X" indicate the presence of obstacles. The left figure corresponds to the first two datasets of Sample Input. In these datasets, the initial position of the bug is $$$(0, 1)$$$, and it moves to $$$(1, 1)$$$ and then to $$$(2, 1)$$$. Next, it attempts to move to $$$(3, 1)$$$, but since there is an obstacle there, it turns to the positive direction of y and moves to $$$(2, 2)$$$. The points the bug traverses are shown with orange circles. The right figure shows the next two datasets.

Figure D-1: The first two datasets of Sample Input (top) and the next two datasets (bottom)
Input

The input consists of multiple datasets, each in the following format. The number of datasets does not exceed $$$200$$$.

$$$n$$$
$$$a$$$ $$$b$$$ $$$d$$$
$$$x_1$$$ $$$y_1$$$
$$$\vdots$$$
$$$x_n$$$ $$$y_n$$$

Here, $$$n$$$ represents the number of obstacles, which is an integer ($$$1 \le n \le 1000$$$). Both $$$a$$$ and $$$b$$$ are integers between $$$0$$$ and $$$100$$$, inclusive, and the initial position of the bug is at coordinates $$$(a, b)$$$. Additionally, $$$d$$$ represents the distance to move, which is an integer ($$$1 \le d \le 10^{18}$$$).

The $$$i$$$-th obstacle is located at coordinates $$$(x_i, y_i)$$$ ($$$i = 1, \ldots, n$$$). $$$x_i$$$ and $$$y_i$$$ are integers between $$$0$$$ and $$$100$$$, inclusive. No two obstacles are at the same location, that is, if $$$i \not= j$$$, then $$$(x_i, y_i) \not= (x_j, y_j)$$$. Additionally, no obstacle is located at the initial position $$$(a, b)$$$ of the bug. It is guaranteed that the bug can move distance $$$d$$$ or more under the given configuration.

The end of the input is indicated by a line consisting of a zero.

Output

For each dataset, output two integers separated by a space on a single line representing the $$$x$$$- and $$$y$$$-coordinates of the position of the bug after it has moved distance $$$d$$$.

Example
Input
2
0 1 4
3 1
2 5
2
0 1 9
3 1
2 5
12
2 2 11
0 1
0 2
0 3
4 1
4 2
4 3
3 4
2 4
1 4
3 0
2 0
1 0
12
2 2 7791772263873
0 1
0 2
0 3
4 1
4 2
4 3
3 4
2 4
1 4
3 0
2 0
1 0
3
0 3 198
99 2
100 3
99 4
3
0 3 1000000000000000000
99 2
100 3
99 4
1
99 100 1
100 100
0
Output
2 3
-2 4
2 3
3 2
0 3
-999999999999999802 3
99 101