Задача E. Интернет на черный день ≡

Условие

В городе Шахматовске два интернет-провайдера выполняют план по всеобщей интернетизации страны. Город расположен на бесконечной целочисленной решетке, по всем линиям которой проходят прямые улицы, а единичные квадраты сетки определяют кварталы. Координатами квартала считаются координаты вершины левого нижнего угла соответствующего единичного квадрата. Кварталы города окрашены в черный и белый цвета в шахматном порядке, при этом квартал с координатами (0, 0) окрашен в черный цвет.

Интернет-провайдер "Черный интернет" занимается подключением кварталов черного цвета. Недавно стало известно, что жителям квартала, подключенного K-м, будет предоставлена скидка в 10%.

В соответствии с планом компании "Черный интернет" интернетизация будет проводиться в течение N дней. В i-й день бригада сотрудников компании движется по какой-то из улиц города, начиная из точки (x_i, y_i). Бригада проходит l_i кварталов в заданном направлении. При этом она подключает ранее не подключенные кварталы черного цвета, граничащие по стороне с путем движения бригады (см. рис.).

Требуется написать программу, которая определит координаты квартала, подключенного во время реализации плана K-м по очереди. Гарантируется, что в процессе реализации плана будет подключено не менее K кварталов.

Формат входного файла

В первой строке входного файла заданы два целых числа N и K (1 ≤ N ≤ 2000, 1 ≤ K ≤ 10¹⁸).

Далее следуют N строк с описанием плана развития компании. В i-й строке описания плана записан путь бригады в i-й день: x_i и y_i (−10¹⁵?y_i, x_i?10¹⁵) — координаты начальной точки пути, символ c_i — направление движения, и l_i (1 ≤ l_i ≤ 10¹⁵) — расстояние, которое пройдет бригада. Направление движения задается одним из следующих символов: "N" — север (по увеличению y-координаты), "E" — восток (по увеличению x-координаты), "S" — юг (по уменьшению y-координаты), "W" — запад (по уменьшению x-координаты).

Формат выходного файла

Выведите в выходной файл координаты x и y квартала, подключенного K-м.

Примеры тестов

4 10
2 0 N 5
2 3 E 3
4 3 S 2
0 1 E 5

4 0

4 7
-1 0 E 4
-1 1 E 4
-1 0 E 4
-1 -1 E 4

0 -2