Полигон — это не только лучшая платформа для разработки задач, но и квадратная матрица со стороной $$$n$$$, изначально состоящая из нулей.

На полигоне проводятся боевые учения. Поэтому над каждой клеткой в первой строке и слева от каждой клетки первого столбца находится пушка. Таким образом, всего есть $$$2n$$$ пушек.

Изначальный полигон для $$$n=4$$$.

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

Более формально:

• если пушка, стоящая в строке $$$i$$$ перед первым столбцом, стреляет единицей, то единица начинает свой полет из клетки ($$$i, 1$$$) и заканчивает в какой-то клетке ($$$i, j$$$);
• если пушка, стоящая в столбце $$$j$$$ над первой строкой, стреляет единицей, то единица начинает свой полет из клетки ($$$1, j$$$) и заканчивает в какой-то клетке ($$$i, j$$$).

Например, рассмотрим следующую последовательность выстрелов:

1. Стреляет пушка в строке $$$2$$$.                         2. Стреляет пушка в строке $$$2$$$.                         3. Стреляет пушка в столбце $$$3$$$.

У вас на столе лежит отчет с проведенных учений. Этот отчет является квадратной матрицей с длиной стороны $$$n$$$, состоящей из нулей и единиц. Вам интересно, действительно ли произошли учения. Другими словами, существует ли такая последовательность выстрелов, что в конце получится заданная матрица?

Каждая пушка может сделать произвольное количество выстрелов. Перед началом учений полигон состоит из нулей.