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

Автор:Жюри ROI-2007   Ограничение времени:1 сек
Входной файл:internet.in   Ограничение памяти:256 Мб
Выходной файл:internet.out  
Максимальный балл:100  

Условие

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

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

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

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

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

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

Далее следуют N строк с описанием плана развития компании. В i-й строке описания плана записан путь бригады в i-й день: xi и yi (1015?yi, xi?1015) — координаты начальной точки пути, символ ci — направление движения, и li (1 ≤ li ≤ 1015) — расстояние, которое пройдет бригада. Направление движения задается одним из следующих символов: "N" — север (по увеличению y-координаты), "E" — восток (по увеличению x-координаты), "S" — юг (по уменьшению y-координаты), "W" — запад (по уменьшению x-координаты).

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

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

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

Входной файл (internet.in) Выходной файл (internet.out)
1
4 10
2 0 N 5
2 3 E 3
4 3 S 2
0 1 E 5
4 0
2
4 7
-1 0 E 4
-1 1 E 4
-1 0 E 4
-1 -1 E 4
0 -2

0.043s 0.007s 17