Задача №25. Интернет на черный день
|
В городе Шахматовске два интернет-провайдера выполняют план по всеобщей интернетизации страны. Город расположен на бесконечной целочисленной решетке, по всем линиям которой проходят прямые улицы, а единичные квадраты сетки определяют кварталы. Координатами квартала считаются координаты вершины левого нижнего угла соответствующего единичного квадрата. Кварталы города окрашены в черный и белый цвета в шахматном порядке, при этом квартал с координатами (0, 0) окрашен в черный цвет.Интернет-провайдер «Черный интернет» занимается подключением кварталов черного цвета. Недавно стало известно, что жителям квартала, подключенного K-м, будет предоставлена скидка в 10%. В соответствии с планом компании «Черный интернет» интернетизация будет проводиться в течение N дней. В i-й день бригада сотрудников компании движется по какой-то из улиц города, начиная из точки (xi, yi). Бригада проходит li кварталов в заданном направлении. При этом она подключает ранее не подключенные кварталы черного цвета, граничащие по стороне с путем движения бригады (см. рис.). Требуется написать программу, которая определит координаты квартала, подключенного во время реализации плана K-м по очереди. Гарантируется, что в процессе реализации плана будет подключено не менее K кварталов. |
|
В первой строке задаются два целых числа N и K (1 ≤ N ≤ 2 000, 1 ≤ K ≤ 1018).
Далее следуют N строк с описанием плана развития компании. В i-й строке описания плана записан путь бригады в i-й день: xi и yi (–1015 ≤ xi ≤ 1015, –1015 ≤ yi ≤ 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