Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

Когда луч приходит в угол, через который проходят зеркальные стены, дальше он идет так, как показано на рисунках (серым цветом показаны клетки, которые окружены зеркальными стенами). Аналогичным образом луч ведет себя, когда приходит на границу лабиринта.

Мальчику Васе очень нравится известная игра «Сапер». В нее играет один человек. Игра идет на клетчатом поле размером \(m\)×\(n\) (\(m\) строк, \(n\) столбцов). В некоторых клетках поля стоят мины. В каждой из остальных клеток записано либо число от 1 до 8 – количество мин в соседних с ней клетках, либо ничего не написано – это означает, что в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую вершину. В одной клетке не может стоять более одной мины. Будем называть поле с расположенными на нем минами и числами картой.

Изначально все клетки поля закрыты. Игрок за один ход может открыть какую-нибудь клетку. После этого игроку показывается содержимое этой клетки, и если в открытой им клетке оказывается мина, он проигрывает. В противном случае игра продолжается. Цель игры – открыть все клетки, в которых нет мин.

У Васи на компьютере есть эта игра, но ему кажется, что все карты, которые в ней есть, некрасивые и неинтересные. Поэтому он решил нарисовать свои. При этом он хочет, чтобы карты, которые он нарисует, после того, как они будут открыты, выглядели красиво.

У Васи есть рисунки, нарисованные на клетчатой бумаге следующим образом: некоторые клетки закрашены в черный цвет, а некоторые оставлены белыми. Вася хочет по каждому такому рисунку сделать соответствующее ему поле для игры в «Сапера» по следующему правилу: если на рисунке клетка покрашена в черный цвет, то на этом месте должна быть либо мина, либо число от 1 до 8, если же клетка оставлена белой, то на игровом поле она должна быть пустой.

Напишите программу, которая сделает это за Васю.

Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.

Магическим квадратом называют таблицу, в которой записаны числа \(1, 2, 3, …\) по одному разу, так что сумма чисел в каждой строке и в каждом столбце равные. Мы расскажем вам об одном из методов построения магических квадратов (его называют сиамским). Он годится только для построения квадратов с нечетной стороной \((3\times 3, 5\times 5, …)\).

Поставим число \(1\) в верхнюю клетку центрального столбца. Далее будем двигаться по диагонали вправо-вверх, расставляя в клетки последовательно числа \(2, 3, 4, …\). Если мы вышли за пределы таблицы вверх, то нужно перейти к нижней клетке того же столбца и продолжить с нее. Если мы вышли за правую границу, нужно перейти к левой клетке той строки, куда мы должны были попасть. Если же мы одновременно вышли и вверх, и вправо, то нужно перейти в левую нижнюю клетку квадрата.

Если в следующей клетке на нашем пути уже стоит число, то вместо хода “вправо-вверх” нужно сделать ход “вниз” (опять же, если мы при этом выйдем за границы квадрата, нужно перейти к верхней клетке того же столбца). Примеры для квадратов \(3\times 3\) и \(5\times 5\) показаны на рисунках.