Coins

There are coins placed on squares of a $N \times N$ grid board where $N$ is even. There is one coin in each square. Exactly half of the coins are silver ones, the other half are copper.

The coins are placed properly if all the copper coins are in the upper left part of the board and silver coins are placed on the lower right part of the board. To be precise, if the edge of a square is a separator between different types of coins, the copper coin is either to the left or above the silver coin.

Proper placement	Improper placement

Figure 1: The coins are placed properly if there are no placements as shown on the right. Black circles represent copper coins, white circles represent silver ones.

You are given a set of coins placed improperly on the board. Rearrange them to get a proper placement by switching as few pairs of coins as possible.

The first line contains four integers $T$, $N$, $K_1$, $K_2$.

• $T$ is the number of the test.
• $N$ is the board size.
• $K_1$ and $K_2$ are values that define grading (see the Grading section).

Each of the remaining $N$ lines contains $N$ integers. They describe the initial coin placement on the board. Each integer is either 0 (copper coin) or 1 (silver coin).

Output the board with a proper placement of coins in the same format as the input, as an $N \times N$ board. Exactly half of the integers are 0 (copper coin), and the other half are 1.