21712번 - Интернет на черный день 다국어

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

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

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

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

Рисунок к примеру 1

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

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

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