Ma phương (ma trận kỳ ảo hay hình vuông ma thuật) là một bài toán sắp xếp ~n^2~ số nguyên phân biệt trong đoạn ~[1;n^2]~ vào một hình vuông với mỗi cạnh chứa ~n~ ô vuông con. Điểm đặc biệt của bài toán đó là tổng ~n~ số trên mỗi hàng, cột, và đường chéo đều bằng nhau.

Ta dễ dàng chứng minh rằng: Tồn tại ma trận kì ảo chuẩn cho mọi bậc ~n \ge 1~ ngoại trừ ~n = 2~. Ma trận kì ảo bậc ~1~ là trường hợp không đáng kể, nó chứa duy nhất một ô với giá trị ~1~. Trường hợp không tầm thường có kích thước nhỏ nhất là ma trận kì ảo bậc ~3~.

Hằng số là tổng của mỗi hàng, cột, và đường chéo được gọi là hằng số kì ảo. Giá trị này của ma trận kì ảo chuẩn chỉ phụ thuộc vào ~n~ và có giá trị là: $$\mathcal{M} = \sum^n = \frac{n(n^2+1)}{2} = \text{Constant}$$

Theo đó, với các ma trận kì ảo bậc ~n = 3, 4, 5, …~ thì các hằng số kì ảo tương ứng là:

Theo tính toán:

• Bảng ~3 \times 3~ có ~1~ ma phương;
• Bảng ~4 \times 4~ có ~880~ ma phương;
• Bảng ~5 \times 5~ có ~275305224~ ma phương;
• Bảng ~6 \times 6~ có khoảng ~\text{(approximately)} \approx 1,77 \times 10^{19}~ ma phương.

Bọn mình đã được Hiệp hội những người Nhờn nhất Thế Giới giao cho một ma phương. Tuy vậy, trên đời này làm gì có chuyện dễ ăn như thế, họ sẽ cung cấp cho ta số ~n~ là cạnh của ma phương, và điền vào "một vài" số vào đó sẵn, việc của chúng ta là cần trả về một ma phương phù hợp, tất nhiên cũng có thể bao gồm cả các ma phương không giải được.

Input Specification

• Dòng thứ nhất sẽ cung cấp số nguyên dương ~n~ ~(2 < n \le 9; n \in \mathbb{N})~, là độ dài cạnh của ma phương.
• ~n~ dòng tiếp theo chứa ~n~ cụm ký tự (mỗi cụm ký tự cách nhau bởi ~1~ dấu cách):
  • Nếu ô đó bị bỏ trống, đây là ô mà chúng ta cần điền số vào (nếu tồn tại ma phương hợp lệ), sẽ tượng trưng bằng dấu underscore _;
  • Có một vài ô sẽ được điền sẵn số bởi Hiệp hội những người Nhờn nhất Thế Giới.

Output Specification

• Nếu có ma phương hợp lệ, in ra:
  • Dòng đầu tiên, in ra NOTHUCSULAMOTCAIGIDAY >:3;
  • ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ cụm ký tự là các số nguyên dương hợp lệ được cách nhau bởi ~1~ dấu cách.
• Nếu không có ma phương hợp lệ, in ra COCAINIT D:.

Limitations

• Lưu ý:

  • Subtask 1 sẽ không được tính điểm vì đây là các Cases mẫu từ đề bài.
  • Gọi ~p~ là số lượng ô bị đục khỏi ma phương bởi Hiệp hội những người Nhờn nhất Thế Giới.

• Subtask 1 [~20\%~]:

  • 1.1 [~10\%~]: ~n = 3~ (Sample Case #1, tồn tại ma phương hợp lệ).
  • 1.2 [~10\%~]: ~n = 3~ (Sample Case #2, không tồn tại ma phương hợp lệ).

• Subtask 2 [~30\%~]: ~n \in \{3; 4; 5\}; p = 0~.

• Subtask 3 [~20\%~]: ~n \in \{3; 4; 5\}; 1 \le p \le \left\lfloor \dfrac{n^2}{2} \right\rfloor~.
• Subtask 4 [~20\%~]: ~n \in \{5; 6; 7\}; \left\lfloor \dfrac{n^2}{2} \right\rfloor \le p \le n^2 - 3~.
• Subtask 5 [~20\%~]: Không có điều kiện gì thêm. Tức theo dữ kiện đề bài: ~2 < n \le 9; 0 \le p \le n^2 - 2~.

Sample Case(s)

Input #1:

3
2 _ _
_ 5 1
_ 3 _

Output #1:

NOTHUCSULAMOTCAIGIDAY >:3
2 7 6
9 5 1
4 3 8

Input #2:

3
5 _ _
_ 1 _
_ _ _

Output #2:

COCAINIT D: