Карта шахты
После недавней кражи набора задач для финала ACM ICPC, совершенной печально известным британским супершпионом Джеймсом Б. (мы сообщали об этом несколько недель назад), ACM решила хранить все будущие наборы задач в здании с высокой степенью безопасности. Совет безопасности, ответственный за создание этого нового хранилища, предложил блестящую идею построить его в форме гигантского лабиринта. Этот лабиринт состоит из множества квадратных комнат, расположенных в виде квадратной матрицы, причем все комнаты соединены друг с другом рядом дверей. Пройти через них — единственный способ добраться до центра, где хранятся наборы задач.
Очевидно, что пройти через лабиринт, в котором все комнаты соединены друг с другом, не так уж и сложно. Поэтому, чтобы сделать его более опасным для потенциальных злоумышленников, некоторые комнаты заминированы. Если кто-то входит в центральную комнату хранилища, содержащую наборы задач, эти мины активируются. После этого открытие двери, ведущей в комнату с миной, вызовет сигнал тревоги, и все двери безопасности немедленно закроются, заперев злоумышленника. Таким образом, ACM может выяснить, кто отправил шпиона, и дисквалифицировать все команды этой страны.
Но недавно совет безопасности узнал о новом сканирующем устройстве, способном обнаруживать мины после их активации. Этот детектор можно использовать из любой комнаты хранилища, и он сможет сообщить пользователю, содержит ли какая-либо из восьми соседних комнат мину или нет. К сожалению, совет уже заказал партию этих мин и теперь не хочет признавать, что это могло быть ошибкой. Вместо этого они просто хотят разместить мины таким образом, чтобы было трудно покинуть центр, просто используя устройство. Вам поручено присоединиться к команде, строящей хранилище, чтобы помочь им оценить их проекты.
Хранилище имеет форму четырехугольника со сторонами нечетной длины. Каждая комната в хранилище может быть описана парой координат, указывающих горизонтальное и вертикальное смещение относительно фиксированного угла здания. В каждой комнате есть двери, ведущие в соседние комнаты; более важно, что детектор мин может обнаруживать мины во всех восьми соседних комнатах. Устройство может только сообщить вам, есть ли поблизости мины, но не сколько их.
Ваша задача — создать специальную карту из каждого чертежа хранилища. На карте отметьте все комнаты, которые кто-то, начиная с центральной комнаты (которая гарантированно не содержит мин), мог бы безопасно достичь с помощью нового детектора и следующей простой стратегии: если вы находитесь в комнате, где детектор сообщает об отсутствии соседних мин, исследуйте все окружающие комнаты. В противном случае не рискуйте активировать мину и не продвигайтесь дальше из этой комнаты (вы можете достичь одной из окружающих комнат через другой "безопасный" маршрут позже).
Таким образом, если злоумышленник находится в комнате, не соседствующей с минами, он сможет перейти во все окружающие комнаты — отметьте такую комнату ".". Если злоумышленник входит в комнату, которая соседствует с одной или несколькими минами, он отступит — отметьте эти комнаты "#". Чтобы иметь возможность проверить вашу работу, совет безопасности также хочет, чтобы вы отметили положение каждой мины "*". Наконец, все оставшиеся комнаты следует отметить "?".
Входные данные
Первая строка содержит количество сценариев. Каждый сценарий начинается с строки, содержащей нечетное целое число n (1 < n < 300) хранилища, указывающее длину одной из его внешних стен. Далее следует число m мин (которое положительно и ограничено только количеством комнат в хранилище). Затем идет m строк, каждая из которых содержит два целых числа r и c (1 ≤ r, c ≤ n), которые указывают рядок и столбец мины.
Выходные данные
Вывод для каждого сценария начинается со строки, содержащей "Сценарий #i:", где i — номер сценария, начиная с 1. Затем выведите ASCII-представление карты хранилища, как описано выше. Завершите вывод для сценария пустой строкой.