Screensaver

Bajtazar just started a new job at a 3D-graphics company and received a new computer with an enormous-resolution monitor. To test the hardware, he decided to write a screensaver based on the classic idea of a ball bouncing around the screen.

Every wall is a horizontal or vertical segment, and no two walls share any common point. The ball always travels at a 45-degree angle to the walls and bounces according to the law of reflection: it always reflects at 45 degrees to the surface it hits, whether it strikes the middle of a wall or one of its endpoints.

Given the arrangement of the walls and a time $t$, determine the position of the ball after the screensaver has been running for $t$ byte-seconds.

The first line contains three integers $s$ ($1 \le s \le 50000$), $k$ ($0 \le k \le 3$) and $t$ ($0 \le t \le 10^{18}$): the number of walls, the ball's initial direction of movement, and the time (in byte-seconds) at which its position is requested. The directions $k$ mean:

• $0$: north-east ($x$ and $y$ both increase)
• $1$: south-east ($x$ increases, $y$ decreases)
• $2$: south-west ($x$ and $y$ both decrease)
• $3$: north-west ($x$ decreases, $y$ increases)

Each of the next $s$ lines contains four integers $p_x$, $p_y$, $k_x$, $k_y$ ($0 \le p_x, p_y, k_x, k_y \le 10^9$): the coordinates of the two endpoints of one wall. The total length of the walls $l$ and the number of walls $s$ satisfy $l + s \le 100000$. The ball starts from the midpoint of the first wall, moving in direction $k$, and in each byte-second it moves one unit along both the $x$ and $y$ axes. The length of the first wall (the one the ball starts from) is always even.

Print, on a single line, the position of the ball at time $t$: two integers, the $x$ and $y$ coordinates, separated by a single space.