Polygon

Polygon is not only the best platform for developing problems but also a square matrix with side $$$n$$$, initially filled with the character 0.

On the polygon, military training was held. The soldiers placed a cannon above each cell in the first row and a cannon to the left of each cell in the first column. Thus, exactly $$$2n$$$ cannons were placed.

Initial polygon for $$$n=4$$$.

Cannons shoot character 1. At any moment of time, no more than one cannon is shooting. When a 1 flies out of a cannon, it flies forward (in the direction of the shot) until it collides with a polygon border or another 1. After that, it takes the cell in which it was before the collision and remains there. Take a look at the examples for better understanding.

More formally:

• if a cannon stands in the row $$$i$$$, to the left of the first column, and shoots with a 1, then the 1 starts its flight from the cell ($$$i, 1$$$) and ends in some cell ($$$i, j$$$);
• if a cannon stands in the column $$$j$$$, above the first row, and shoots with a 1, then the 1 starts its flight from the cell ($$$1, j$$$) and ends in some cell ($$$i, j$$$).

For example, consider the following sequence of shots:

1. Shoot the cannon in the row $$$2$$$.                         2. Shoot the cannon in the row $$$2$$$.                         3. Shoot the cannon in column $$$3$$$.

You have a report from the military training on your desk. This report is a square matrix with side length $$$n$$$ consisting of 0 and 1. You wonder if the training actually happened. In other words, is there a sequence of shots such that, after the training, you get the given matrix?

Each cannon can make an arbitrary number of shots. Before the training, each cell of the polygon contains 0.