Sliding Blocks

Rectangular blocks are given one by one in the plane. Every block is parallel to the xy-axis. Each block starts at a given location and moves along a given direction, which is always left-downward. A block's location is the $(x, y)$ coordinate of its lower-left corner.

The movement of a block has two phases.

In the first phase, the block moves from its starting location toward $(x - \Delta x, y - \Delta y)$. While it moves, if its bottom side hits the x-axis or another block, its direction changes to leftward and it enters the second phase. If its left side hits the y-axis or another block, its direction changes to downward and it enters the second phase. If its lower-left corner touches the upper-right corner of another block, it may change to either downward or leftward. Downward has higher priority. If downward is blocked by other blocks, the direction changes to leftward. If the upper-left or lower-right corner of the block only touches another block's corner, the block keeps its direction, because a corner contact does not block it.

In the second phase, the block repeats move-left and move-down (or move-down and move-left) for as long as it can move. Once the block enters the second phase, it keeps moving in the same direction as far as possible. When the x-axis, the y-axis, or another block blocks it, it changes direction and keeps moving.

Figure J.1 shows an example of a block's path. The red line is the path, and the orange block is the final position.

Figure J.2 shows the corner cases described above.

For each block, the following information is given.

1. The width and height $w$ and $h$ of the block.
2. The starting location $(x, y)$.
3. The direction $(\Delta x, \Delta y)$ of the first movement. See Figure J.3. The block begins at $(x, y)$ and moves toward $(x - \Delta x, y - \Delta y)$.

Given the information on $n$ blocks, find the location of the last block after every block has moved one by one according to the rules above. The $i$th block (for $2 \le i \le n$) does not overlap any earlier block at its starting location. Some blocks may not move at all from their starting location because other blocks block them.

The first line contains an integer $n$ ($1 \le n \le 1{,}000$), the number of blocks. Each of the next $n$ lines contains six integers $w$, $h$, $x$, $y$, $\Delta x$, $\Delta y$. The width and height satisfy $1 \le w, h \le 100{,}000$. The starting location satisfies $0 \le x, y \le 10^8$. The direction satisfies $1 \le \Delta x, \Delta y \le 10^5$.

Print one line with two integers $x$ and $y$, the location of the last block after all blocks have moved.