24031번 - 카카오 택시

라이언은 Secret Forest에 오기 전, 둥둥섬의 왕위 계승자였다. 하지만, 왕궁에서의 반복되는 일상의 지루함을 느끼던 어느 날, 라이언은 둥둥섬 탈출을 감행한다.

둥둥섬의 교통체계는 $N$개의 교차로가 수직, 수평 방향 도로로 연결되어 있는 형태로, 교차로들은 1m 간격으로 구성된 좌표평면 위에서 $x$, $y$ 좌표가 짝수인 점들로 표현할 수 있다. 임의의 두 교차로 $(x_i, y_i)$, $(x_j, y_j)$가 $x_i=x_j$, $|y_i-y_j|=2$를 만족하면 두 사거리 사이에 세로 방향 도로가 존재하고, $y_i=y_j$, $|x_i-x_j|=2$를 만족하면 두 사거리 사이에 가로 방향 도로가 존재한다. 또한 어떤 교차로에서 다른 어떤 교차로로 가로, 세로 도로만을 이용하여 이동할 수 있음이 보장된다.

또한, 각 교차로마다 신호등이 있는데, 신호등은 $K$초를 주기로 일정한 패턴이 반복된다. 임의의 시간에서 신호등의 상태는 다음 그림과 같이 1, 2, 3, 4의 4가지 상태로 표현할 수 있고, 신호에 따라 통행할 수 있는 차량의 방향이 달라진다. 예를 들어, $K=3$이고 한 교차로의 신호 패턴이 "132"라면 0초에서 1초 사이의 1초 동안은 1번 상태, 1초에서 2초 사이의 1초 동안은 3번 상태, 2초에서 3초 사이의 1초 동안은 2번 상태, 3초에서 4초 사이의 1초 동안은 1번 상태, ... 등으로 무한히 반복된다.

신호의 상태에 따른 차량의 이동 방향은 위 그림과 같다.

둥둥섬에서 가장 사랑받는 교통수단인 카카오 T택시는 어떤 도로의 중점에서 특정 방향으로 출발하며, 1초에 2m씩 이동하고, 교차로에서 방향을 바꾸거나 새로운 도로로 진입하는데 걸리는 시간은 무시할 수 있다. 일반적인 도시들과는 다르게, 둥둥섬에는 특별한 교통법이 있어 차량이 교차로를 통과할 때 다음 조건을 지키며 이동해야 한다. 가장 먼저, 모든 차량은 신호 대기 이외의 이유로는 멈출 수 없다. 또한, 자신이 진입할 교차로의 신호의 방향이 현재 차량의 위치에서 진입할 수 있는 방향이며, 진입한 후 나가는 방향의 도로도 있다면 바로 해당하는 방향의 도로로 나간다. 신호의 방향이 현재 차량의 위치에서 진입할 수 없는 방향이거나, 진입 하더라도 나가는 방향의 도로가 없다면 이동할 수 있는 신호가 오기까지 교차로에 진입하지 않고 기다렸다가 신호가 바뀌는 순간 출발한다. 추가로, 만약 현재 위치에서 진입할 교차로에서 아무리 오래 기다리더라도 신호 패턴의 구조상 더 이상 이동할 수 없다면 그 교차로까지 이동한 이후, 교차로에서 즉시 유턴하여 돌아나온다. 따라서, 차량은 임의의 정수 시간에 격자점에 위치하게 되며, $x$좌표와 $y$좌표의 기우성이 다르다.

탈출을 위해 다사다난한 하루를 보낸 라이언은 카카오택시에서 결국 잠이 들어 버리고 말았다. 라이언이 눈을 떴을 때, $T$초가 흘러 있다는 사실을 알아차렸다. 라이언이 처음 카카오택시를 탔을 때의 좌표와 출발 방향을 알고 있을 때, 현재 위치를 알 수 있도록 도와주자.

첫 번째 줄에 $N$, $K$이 입력으로 주어진다. ($1 \leq N \leq 100,000$, $1 \leq K \leq 10$)

두 번째 줄부터 $N$개의 줄에 걸쳐 교차로의 정보가 $x_i$, $y_i$로 주어진 후, 그 줄에 이어 신호 패턴 $s_{i1}s_{i2}\cdots s_{iK}$이 공백 없이 주어진다. ($0 \leq x_i, y_i \leq 200,000$, $x_i$, $y_i$는 짝수, $s_{ij} \in \{1, 2, 3, 4\}$)

어떤 교차로에서 다른 어떤 교차로로 가로, 세로 도로만을 이용하여 이동할 수 있음이 보장된다.

그 후 라이언이 처음 카카오택시를 탔을 때의 좌표 $sx$, $sy$이 주어지고 그 줄에 이어 카카오택시의 출발 방향 $sd$가 주어진다. $+$는 $x$좌표 혹은 $y$좌표가 증가하는 방향을 의미하고 $-$는 $x$좌표 혹은 $y$좌표가 감소하는 방향을 의미한다. ($0 \leq sx, sy \leq 200,000$, $sx$, $sy$는 홀짝성이 다름, $sd \in \{+, -\}$)

$(sx, sy)$는 어떤 도로 위임이 보장된다.

마지막 줄에는 출발 이후 지난 시간 $T$가 주어진다. ($0 \leq T \leq 10^{18}$)

첫번째 줄에 현재 카카오택시의 위치 $(x, y)$를 공백을 사이에 두고 출력한다.