Задача R. Марсоход

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

Условие

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

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

Известно, что марсоход высадился где-то в прямоугольнике с координатами (x1, y1) − (x2, y2). К сожалению связь с марсоходом была потеряна по неизвестным причинам, но он успел передать, что полностью выполнил программу движения. Удалось также определить, что последний сигнал был послан из прямоугольника с координатами (x3, y3) − (x4, y4). Ученые хотят сократить зону поиска и просят вас написать программу, определяющую, на каких участках этого прямоугольника может находиться марсоход.

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

В первой строке входного файла содержатся целые числа x1 y1 x2 y2 x3 y3 x4 y4, во второй строке содержится программа марсохода.

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

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

Ограничения

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

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

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

0.039s 0.008s 15