Павел создал лучшую игру в мире —«Деление пополам». В этой игре игроку дано квадратное клеточное поле размера n × n. Некоторые из клеток поля помечены и образуют фигуру. От игрока требуется покрасить каждую из клеток этой фигуры в один из двух цветов так, чтобы получившиеся фигуры обоих цветов были бы равны. Фигуры называются равными, если одну из них можно совместить с другой посредством параллельных переносов, отражений относительно горизонтальных и вертикальных осей и поворотов на углы, кратные 90 градусам.
Павел придумал еще один уровень для этой игры, но никак не может понять, имеет ли он решение. Вам предстоит это выяснить.
В первой строке записано целое число n (1 ≤ n ≤ 50) — размер поля.
В каждой из следующих n строк записано по n символов. Символ «.» означает, что клетка не принадлежит фигуре, а «#» — что принадлежит.
Гарантируется, что во входных данных присутствует четное положительное количество символов «#».
Если решения не существует, выведите «NO» (без кавычек).
Иначе выведите «YES» (без кавычек), а затем n строк по n символов, описывающих раскраску клеток фигуры. Символы «.» из входных данных оставьте без изменения, а символы «#» замените на «A» или «B», в зависимости от того, в какой цвет надо покрасить данную клетку.
Если существует несколько решений, выведите любое.
3
{.##}
{###}
{###}
YES
.AA
BAB
BBA
3
{###}
{.##}
{###}
NO
