Một con chuột robot được đặt ở góc trên bên trái ô \((1, 1)\) của một mê cung kích thước \(N \times N\). Robot chỉ được phép di chuyển sang phải hoặc xuống dưới. Mê cung có một số ô bị cản trở không thể đi qua (được đánh dấu bằng số 0, các ô đi được đánh dấu bằng số 1). Hãy tìm đường đi từ ô \((1, 1)\) đến ô góc dưới bên phải \((N, N)\) và in ra lộ trình di chuyển. Nếu có nhiều đường đi, hãy chọn bất kỳ đường nào. Nếu không thể đi tới đích, hãy báo cáo lại.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên 0 hoặc 1 cách nhau bởi dấu cách biểu thị sơ đồ mê cung. Ô xuất phát \((1, 1)\) và ô đích \((N, N)\) luôn bằng 1.

Định dạng đầu ra

• Nếu tồn tại đường đi, in ra mê cung kích thước \(N \times N\) trong đó các ô nằm trên đường đi được đánh dấu bằng số 9, các ô khác giữ nguyên giá trị ban đầu.
• Nếu không có đường đi, in ra -1.

Ví dụ

Input:

4
1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

Output:

9 0 0 0
9 9 0 1
0 9 0 0
1 9 9 9