Plant Trees on an Obstacle Grid

You are given a square grid of size (n \times n) where each cell is either an available plot represented by (0) or an occupied plot represented by (X). Your task is to determine whether it is possible to plant trees on the grid so that exactly one tree (denoted by (T)) is placed in each row and each column, while ensuring that no tree is planted on an occupied cell.

In other words, you must assign exactly one cell per row and per column to contain a tree, and that cell must not initially be occupied. If such a configuration exists, output the modified grid; otherwise, output the string "Not possible".

Constraints: (2 \le n \le 10).

inputFormat

Input is read from standard input (stdin). The first line contains an integer (n), the size of the grid. This is followed by (n) lines, each containing (n) space-separated tokens where each token is either (0) or (X).

outputFormat

If a valid tree placement configuration is found, output (n) lines, each representing a row of the grid with the tree placements (the cell with a tree is marked with (T)). Otherwise, output the string "Not possible". All output should be written to standard output (stdout).## sample

3
0 0 X
X 0 0
0 X 0

T 0 X
X T 0
0 X T