ЗАДАЧА I
Поиски клада
| Имя входного файла: | treasure.in |
| Имя выходного файла: | treasure.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Тут дядя Федор вмешался:
- Никого мы продавать не будем. Мы пойдем клад искать.
- Ура! - кричит Шарик. - Давно пора! - А сам потихоньку у кота спрашивает: - А что такое склад?
- Не склад, а клад, - отвечает кот. - Это деньги такие и сокровища, которые люди в землю спрятали. Разбойники всякие.
Э.Успенский «Дядя Федор, пес и кот», глава 4
Но прежде чем искать клад, нужно было узнать, где он спрятан. «А давайте на чердаке покопаемся – там много разных старых вещей лежит, может и карта клада найдется», – предложит Матроскин. И действительно, после нескольких часов упорных поисков дядя Федор с Шариком нашли старинный сундук, в котором лежала потертая карта опушки простоквашинского леса с какими-то пометками. Сбоку на карте был нарисован компас, показанный на рисунке.
Оказалось, что на карте отмечено N ориентиров и точка, с которой нужно начинать поиски. На обороте карты друзья обнаружили список из M инструкций. Инструкции были следующих типов:
1. «Пройдите на N/S/W/E на X метров», где X является натуральным числом, – означает, что нужно продвинуться на указанное число метров в указанном направлении, не обращая внимания на ориентиры.
2. «Пройдите на NE/SE/NW/SW на X метров», где X является натуральным числом, – означает, что нужно продвинуться на указанное число метров в указанном направлении, не обращая внимания на ориентиры.
3. «Двигайтесь в направлении N/W/S/E/NE/SE/NW/SW до ближайшего ориентира» – следует перемещаться в указанном направлении до попадания в точку, где находится какой-то ориентир.
Матроскин внимательно осмотрел инструкции и сказал: «Н-да, да тут целую неделю можно ходить туда-сюда, но так не пойдет. Лучше мы сначала посчитаем, где именно закопан клад, а потом сразу придем в нужную точку и выкопаем его». Помогите Матроскину вычислить координаты клада.
Введем для удобства на опушке леса декартову систему координат так, чтобы начальная точка поисков имела координаты (0, 0), а положительное направление оси OY совпадало с направлением на север.
Входные данные
Первая строка входного файла содержит единственное целое число N (0 <= N <= 1000) – количество ориентиров. Каждая из следующих N строк содержит два целых числа, по модулю не превосходящих 10000 – координаты Xi, Yi ориентиров. Никакие два ориентира не совпадают, и ни один ориентир не находится в точке (0,0).
Следующая строка содержит единственное натуральное число M (0 <= M <= 1000) – количество инструкций. Последующие M строк содержат инструкции, по одной в строке. Инструкции типа 1 (см. выше) задаются строкой “D X”, где D – символ “N”, “S”, “E” или “W”, а X – натуральное число, не превосходящее 10000. Инструкции типа 2 задаются строкой “DD X”, где DD – два символа “NE”, “SE”, “NW” или “SW”, а X – натуральное число, не превосходящее 10000. Инструкции типа 3 задаются строкой “DD GO”, где DD – это один или два символа “N”, “S”, “E”, “W”, “NE”, “SE”, “NW” или “SW”. Все элементы в строке разделяются одним пробелом.
Выходные данные
В единственную строку выходного файла выведите два целых числа – координаты точки, где закопан клад.
Пример
| treasure.in | treasure.out |
|---|---|
|
|