Альянсы
В фантастическом мире существует большой остров прямоугольной формы. Стороны острова имеют длину ровно R миль и C миль, и весь остров разделён на сетку из R×C участков. Некоторые из участков необитаемы, а остальные заняты деревнями фантастических существ: эльфов, людей, гномов и хоббитов. В каждом участке может находиться не более одной деревни. Две деревни считаются соседними, если их участки имеют общую сторону.
Недавно деревни были напуганы Великим Злом. Чтобы чувствовать себя в безопасности, каждая деревня решила заключить военные союзы с некоторыми из своих соседей. Союз всегда включает две соседние деревни и является взаимным и симметричным соглашением.
В зависимости от вида, живущего в деревне, жители не будут чувствовать себя в безопасности, если не будет сформирована определённая конфигурация союзов:
Эльфы уверены в себе и поэтому нуждаются ровно в одном союзе.
Деревни людей требуют союзов ровно с двумя соседями. Более того, оставлять две противоположные стороны деревни незащищёнными плохо по тактическим причинам. Поэтому два союзных соседа не могут находиться на противоположных сторонах деревни.
Гномы требуют союзов ровно с тремя соседями.
Хоббиты крайне напуганы и поэтому нуждаются в союзах со всеми четырьмя своими соседями.
Другими словами, за исключением людей, каждая деревня требует определённого количества союзов, но не заботится о том, какие соседи будут её союзниками. Для людей есть дополнительное ограничение: союзные соседи не должны находиться на противоположных сторонах деревни.
Условия должны быть выполнены независимо от положения деревни на карте. Например, деревня гномов желает три союза. Если она расположена на побережье, это означает, что она должна иметь союзы со всеми тремя соседями. Если деревня гномов находится в углу острова, её жители никогда не будут чувствовать себя в безопасности.
Для данного описания острова ваша задача — решить, возможно ли сформировать союзы так, чтобы все жители острова чувствовали себя в безопасности. В случае положительного ответа, ваша задача также предложить одну жизнеспособную конфигурацию союзов. В случае нескольких решений выберите любое.
Входные данные
Первая строка входных данных содержит два целых числа R и C, указывающих размер острова. Следующие R строк кодируют описание острова. Каждая строка состоит из C чисел, разделённых пробелами, от 0 до 4:
0 означает необитаемый участок,
1 означает деревню эльфов,
2 означает деревню людей,
3 означает деревню гномов,
4 означает деревню хоббитов.
(Обратите внимание, что число во входных данных всегда соответствует количеству желаемых союзов для этой деревни.)
Ограничения
Во всех тестовых случаях предполагается, что 1 ≤ R, C ≤ 70.
В тестовых случаях, стоящих в общей сложности 55 баллов, min(R, C) ≤ 10. Из них в тестовых случаях, стоящих 15 баллов, R·C ≤20.
Ещё одна партия тестовых случаев, стоящих 10 баллов, содержит карты только с необитаемыми участками и деревнями людей. (Эта партия не включена в тестовые случаи, стоящие 55 баллов.)
Выходные данные
Если решения нет, выведите одну строку с текстом "Impossible!" (кавычки для ясности). В противном случае выведите одну допустимую карту союзов в следующем формате.
Каждый участок должен появиться в выводе в виде матрицы 3×3 символов. Если участок необитаем, соответствующая часть вывода будет заполнена символами . (точка). Если на участке есть деревня, в центре должен быть символ O (заглавная буква O), представляющий саму деревню, и должны быть символы X (заглавная буква X), представляющие конфигурацию её союзников. Остальная часть матрицы должна быть заполнена символами . (точка).
Для каждого типа деревни все возможные варианты расположения союзов показаны на изображении ниже.
