Задача B. Праздник урожая ≡

Условие

Жители города Фендолин собираются устроить костюмированное шествие в честь дня сбора урожая. Организаторы праздника выбрали для мероприятия маршрут, проходящий по наиболее живописным улицам города. Для того, чтобы каждый желающий мог присоединиться к демонстрации, организаторы планируют напечатать в местной газете план города, на котором будет указан составленный ими маршрут.

Район проведения шествия на плане представляет собой прямоугольную область, поделенную на квадраты. Получившиеся строки и столбцы пронумерованы числами, начиная с 1, от левого верхнего угла плана. Нечётные строки и столбцы являются улицами, не занятое улицами пространство заполнено домами. Улицы на плане изображены символом ‘.’, дома — символом ‘#’. Маршрут задан набором координат квадратов x_s y_s, через которые планируется провести празднующих (перемещение происходит строго по улицам).

Точки начала и окончания шествия обозначены на схеме символом ‘*’. В зависимости от направления движения участок маршрута обозначается символом ‘>’ (вправо), ‘^’ (вверх), ‘<’ (влево) или ‘V’ (вниз). Точки, где маршрут поворачивает или пересекает себя (за исключением пересечения с началом или окончанием маршрута), обозначаются символом ‘X’.

Программа должна вывести план области проведения шествия с нанесённым маршрутом.

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

Первая строка входного файла содержит три натуральных числа N, M и K. Далее следуют K строк, содержащих координаты квадратов x_s, y_s, через которые проходит маршрут.

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

Выходной файл должен содержать 2*M+1 строк длиной по 2*N+1 символов каждая, содержащих ASCII-изображение плана области проведения шествия с нанесённым маршрутом.

Ограничения

2 ≤ N, M ≤ 100, 2 ≤ K ≤ 10

1 ≤ x_s ≤ 2*N+1, 1 ≤ y_s ≤ 2*M+1

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

5 4 6
3 3
9 3
9 9
5 9
5 5
11 5

...........
.#.#.#.#.#.
..*>>>>>X..
.#.#.#.#V#.
....X>>>X>*
.#.#^#.#V#.
....^...V..
.#.#^#.#V#.
....X<<<X..