Страница: << 1 2 Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

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

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

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

Входные данные

В первой строке  задаются два целых числа N и K (1 ≤ N ≤ 2 000, 1 ≤ K ≤ 1018).

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

Выходные данные

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

Примеры
Входные данные
5 19
20 6 S 5
9 7 S 7
9 18 W 1
13 18 N 2
12 13 E 5
Выходные данные
15 13

Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест