Школьники ACM 2005 - Марсоход

Задача D. Марсоход ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	И. Олейников, А. Кленин	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	3 Мб
Выходной файл:	output.txt

Условие

В далеком будущем российские ученые собрали и отправили аппарат для исследования поверхности Марса — "Марсоход-1". Поверхность кратера, в который высадился марсоход, разбита на участки размером 1 x 1 метр каждый. Программа движения марсохода состоит из последовательности команд:

w — передвинуться на 1 метр на запад,
e — передвинуться на 1 метр на восток,
s — передвинуться на 1 метр на юг,
n — передвинуться на 1 метр на север.

Координаты юго-западного угла кратера — (0, 0). Оси координат направлены с запада на восток и с юга на север.

Известно, что марсоход высадился где-то в прямоугольнике с координатами (x₁, y₁) − (x₂, y₂). К сожалению связь с марсоходом была потеряна по неизвестным причинам, но он успел передать, что полностью выполнил программу движения. Удалось также определить, что последний сигнал был послан из прямоугольника с координатами (x₃, y₃) − (x₄, y₄). Ученые хотят сократить зону поиска и просят вас написать программу, определяющую, на каких участках этого прямоугольника может находиться марсоход.

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

В первой строке входного файла содержатся целые числа x₁ y₁ x₂ y₂ x₃ y₃ x₄ y₄, во второй строке содержится программа марсохода.

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

Выходной файл должен содержать abs(y₄ − y₃) + 1 строк по abs(x₄ − x₃) + 1 символов в каждой — изображение зоны поиска, на котором участки, где может находиться марсоход, отмечены символом 'x' (ASCII 120), а остальные — символом '.' (ASCII 46).

Ограничения

0 ≤ x_i, y_i ≤ 1000, количество команд в программе не превышает 30000.

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`1 1 2 2 3 3 4 4 ne`	`.. x.`