화면 보호기

바이트자르(Bajtazar)는 3차원 그래픽을 만드는 회사에 입사하면서 초고해상도 모니터가 달린 새 컴퓨터를 받았다. 그는 새 장비를 시험해 보려고 화면 보호기를 만들기로 했다. 화면 위를 돌아다니는 공이 벽에 부딪혀 튕기는, 고전적인 방식이다.

모든 벽은 수평 또는 수직 선분이고, 어떤 두 벽도 공통점을 가지지 않는다. 공은 항상 벽면에 대해 45도 각도로 움직이며, 반사 법칙에 따라 튕긴다. 즉 벽의 한가운데에 부딪히든 끝점에 부딪히든, 언제나 벽면에 대해 45도로 반사된다.

주어진 벽 배치와 시각 $t$에 대해, 화면 보호기가 작동한 지 $t$ 바이트초가 지난 순간 공의 위치를 구하여라.

첫째 줄에 세 정수 $s$ ($1 \le s \le 50000$), $k$ ($0 \le k \le 3$), $t$ ($0 \le t \le 10^{18}$)가 주어진다. 각각 벽의 개수, 공의 처음 진행 방향, 그리고 위치를 구할 시각(바이트초)이다. 방향 $k$의 의미는 다음과 같다.

• $0$: 북동쪽 ($x$와 $y$가 모두 증가)
• $1$: 남동쪽 ($x$는 증가, $y$는 감소)
• $2$: 남서쪽 ($x$와 $y$가 모두 감소)
• $3$: 북서쪽 ($x$는 감소, $y$는 증가)

이어지는 $s$개의 줄에는 각 벽의 두 끝점 좌표 $p_x$, $p_y$, $k_x$, $k_y$ ($0 \le p_x, p_y, k_x, k_y \le 10^9$)가 주어진다. 모든 벽의 길이 합 $l$과 벽의 개수 $s$는 $l + s \le 100000$을 만족한다. 공은 첫 번째 벽의 중점에서 방향 $k$로 출발하며, 한 바이트초마다 $x$축과 $y$축으로 각각 한 칸씩 이동한다. 공이 출발하는 첫 번째 벽의 길이는 항상 짝수이다.

공이 시각 $t$에 있는 위치를 한 줄에 출력한다. 즉 공의 $x$좌표와 $y$좌표를 공백 하나로 구분한 두 정수로 출력한다.