Fill Enclosed Regions

Given a square matrix of size \(n \times n\) that is initially filled with the digit 0, there exists a closed loop composed of the digit 1. The closed loop can be of any arbitrary shape. The task is to fill all the spaces inside the closed loop (i.e. all 0s that are enclosed by 1s) with the digit 2.

Definition: A cell containing 0 is considered inside the closed loop if, starting from that cell and moving only in the four cardinal directions (up, down, left, right) and passing only through cells with 0, it is impossible to reach the boundary of the matrix. It is guaranteed that all 0s inside the closed loop are connected.

For example, consider the following 6×6 matrix:

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1

After filling, the matrix becomes:

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1

Your task is to implement a program that reads the matrix, fills the enclosed 0s with 2, and outputs the updated matrix.

inputFormat

The first line contains a single integer \(n\) denoting the size of the matrix. Each of the following \(n\) lines contains \(n\) space-separated integers (each either 0 or 1) representing the matrix.

outputFormat

Output the transformed matrix of size \(n \times n\), where each row is printed on a new line with space-separated integers. The 0s that are enclosed by the closed loop of 1s should be changed to 2, while all other digits remain unchanged.

sample

6
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1