검은 날을 위한 인터넷

도시 샤흐마톱스크에는 두 인터넷 제공업체가 있으며, 이들이 전국 인터넷 보급 계획을 수행한다. 도시는 무한한 정수 격자 위에 놓여 있다. 격자의 모든 선을 따라 곧은 도로가 지나고, 단위 정사각형 하나가 구역 하나가 된다. 구역의 좌표는 그 단위 정사각형의 왼쪽 아래 꼭짓점 좌표로 한다. 구역은 체스판처럼 검은색과 흰색이 번갈아 칠해져 있으며, 좌표가 $(0, 0)$인 구역은 검은색이다. 「검은 인터넷」 업체는 검은색 구역을 연결한다. K번째로 연결되는 구역의 주민에게는 10%의 할인이 제공된다. 보급 계획은 N일 동안 진행된다. i일에 공사팀은 $(x_i, y_i)$에서 출발해 도시의 도로 하나를 따라 이동한다. 공사팀은 지정된 방향으로 $l_i$개의 구역을 지나간다. 이때 이동 경로와 변을 맞대고 있으며 아직 연결되지 않은 검은색 구역을 연결한다 (그림 참고). 계획을 실행하는 과정에서 최소 K개의 구역이 연결됨이 보장된다. K번째로 연결되는 구역의 좌표를 구하는 프로그램을 작성하라.

첫 줄에 두 정수 N과 K가 주어진다: $1 \le N \le 2\,000$, $1 \le K \le 10^{18}$. 이어지는 N개의 줄에는 각 날의 이동 경로가 주어진다. 각 줄에는 이동을 시작하는 점 $x_i$와 $y_i$, 이동 방향 문자 $c_i$, 이동 거리 $l_i$가 있다. $-10^{15} \le x_i \le 10^{15}$, $-10^{15} \le y_i \le 10^{15}$, $1 \le l_i \le 10^{15}$이다. 문자 $c_i$는 'N'(북쪽, y 증가), 'E'(동쪽, x 증가), 'S'(남쪽, y 감소), 'W'(서쪽, x 감소) 중 하나이다.

K번째로 연결되는 구역의 x 좌표와 y 좌표를 출력한다.