A Bug That's Not a Pill Bug

Time limit8sMemory limit1024 MB

Summary

Simulate a bug that turns left at obstacles and find its lattice position after it moves exactly d steps, where d can reach 10^18.

Level: Medium5 of 10
Topics: Simulation, Hash map, Implementation
Solved: No attempts yet

Problem

A bug that looks like a pill bug is walking on a plane. A Cartesian coordinate system is defined on the plane, where the $x$ -axis points from west to east and the $y$ -axis points from south to north.

The bug starts at a lattice point (a point whose x and y coordinates are both integers) and faces the positive $x$ direction. Some lattice points have obstacles. The bug keeps moving under the following rules while avoiding obstacles.

The bug tries to move to the adjacent lattice point in the direction it is facing.
If that point has no obstacle, the bug moves there and keeps its direction.
If that point has an obstacle, the bug stays where it is and turns 90 degrees to the left.

The initial position, the obstacle locations, and a distance are given. Find the position of the bug after it has moved exactly that distance.

The figures show some of the sample datasets. In the left figure, the first two datasets start at (0, 1). The bug moves to (1, 1) and then to (2, 1). Next it tries to move to (3, 1), but an obstacle is there, so it turns toward the positive $y$ direction and moves to (2, 2). Points the bug passes through are marked with orange circles. The right figure shows the next two datasets.

Input

The input has multiple datasets, each in the following format. There are at most 200 datasets.

$n$

$a$ $b$ $d$

$x_1$ $y_1$

$\vdots$

$x_n$ $y_n$

Here $n$ is the number of obstacles, an integer from 1 to 1000. $a$ and $b$ are integers from 0 to 100, and the bug starts at $(a, b)$ . $d$ is the distance to move, an integer from 1 to $10^{18}$ . Each obstacle is at $(x_i, y_i)$ , where $x_i$ and $y_i$ are integers from 0 to 100. No two obstacles share a location, and no obstacle is at the starting point. The bug is guaranteed to be able to move distance $d$ or more in this configuration.

The input ends with a line containing a single 0.

Output

For each dataset, print two integers separated by a space on one line: the $x$ and $y$ coordinates of the bug after it has moved distance $d$ . Coordinates can be negative.

Examples1

Example 1

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

Expected output

2 3
-2 4
2 3
3 2
0 3
-999999999999999802 3
99 101