Internet for a rainy day

The city of Shakhmatovsk has two internet providers that are carrying out a nationwide internet rollout plan. The city lies on an infinite integer grid. Straight streets run along every grid line, and each unit square is a block. A block is identified by the coordinates of its lower left corner. The blocks are colored black and white in a checkerboard pattern, and the block at $(0, 0)$ is black. The provider "Black Internet" connects the black blocks. Residents of the block that is connected K-th will receive a 10% discount. The rollout takes N days. On day $i$, a crew starts at $(x_i, y_i)$ and moves along one of the city streets. The crew passes $l_i$ blocks in the given direction. While moving, it connects every black block that is not yet connected and shares a side with the crew's path (see the figure). Write a program that finds the coordinates of the block that is connected K-th. It is guaranteed that at least K blocks are connected during the rollout.

The first line contains two integers N and K: $1 \le N \le 2\,000$, $1 \le K \le 10^{18}$. Each of the next N lines describes the crew's path on one day. The line contains $x_i$ and $y_i$, the starting point of the path, the character $c_i$, the direction of movement, and $l_i$, the distance the crew travels. It is given that $-10^{15} \le x_i \le 10^{15}$, $-10^{15} \le y_i \le 10^{15}$, and $1 \le l_i \le 10^{15}$. The character $c_i$ is one of 'N' (north, y increases), 'E' (east, x increases), 'S' (south, y decreases), or 'W' (west, x decreases).

Print the x and y coordinates of the block that is connected K-th.