Задача B. Ферзи на шахматной доске ≡

Условие

Ферзь — шахматная фигура, которая может двигаться на любое число клеток по горизонтали, вертикали или диагонали.

На бесконечной шахматной доске расположены K ферзей. Требуется вывести прямоугольный фрагмент шахматной доски, заданный двумя противоположными клетками с координатами (X_A; Y_A) и (X_B; Y_B).

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка с ферзем обозначается символом 'X' (ASCII 88), клетка, в которую может походить ферзь обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Клетка с координатами (1; 1) имеет чёрный цвет.

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

Во входном файле содержатся числа X_A Y_A X_B Y_B K

Далее следуют K пар чисел — X_i Y_i

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

Выходной файл должен содержать изображение заданного фрагмента шахматной доски.

Ограничения

1 ≤ X_i, Y_i ≤ 2³¹ − 1

0 ≤ K ≤ 10⁵

1 ≤ |X_A − X_B|, |Y_A − Y_B| ≤ 500

В одной клетке не может находиться более одного ферзя

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

1 8 8 1
2
7 1
3 5

******X*
.#*#.***
*.*.*.*.
.***.#*#
**X*****
.***.#*#
*.*.*.*.
.#*#.**#

6987879 87979870 6987899 87979879
1
3271487 84263477

.*.#.#.#.#.#.#.#.#.#.
#.*.#.#.#.#.#.#.#.#.#
.#.*.#.#.#.#.#.#.#.#.
#.#.*.#.#.#.#.#.#.#.#
.#.#.*.#.#.#.#.#.#.#.
#.#.#.*.#.#.#.#.#.#.#
.#.#.#.*.#.#.#.#.#.#.
#.#.#.#.*.#.#.#.#.#.#
.#.#.#.#.*.#.#.#.#.#.
#.#.#.#.#.*.#.#.#.#.#