Fillomino 2

Cho một bàn cờ kích thước $n\times n$. Các hàng được đánh số từ $1$ đến $n$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $n$ từ trái sang phải. Ô tại giao của hàng $x$ và cột $y$ được ký hiệu $(x,y)$. Đường chéo chính của bàn cờ là tập hợp các ô $(x,x)$ với $1\le x\le n$.

Trên đường chéo chính được ghi sẵn một hoán vị của tập $\{1,2,\dots ,n\}$: ô $(i,i)$ chứa số $p_i$. Bạn cần chia tất cả các ô nằm dưới và trên đường chéo chính (tổng cộng có $1+2+\cdots +n$ ô) thành $n$ vùng thỏa mãn:

1. Mỗi vùng phải liên thông theo 4-hướng (lên, xuống, trái, phải).
2. Với mọi $1\le x\le n$, vùng thứ $x$ phải chứa ô đường chéo có giá trị $x$ (tức là ô $(i,i)$ sao cho $p_i=x$).
3. Với mọi $1\le x\le n$, vùng thứ $x$ có đúng $x$ ô.
4. Mỗi ô nằm dưới hoặc trên đường chéo chính thuộc về đúng một vùng.

Có thể chứng minh rằng với mọi hoán vị $p$ luôn tồn tại cách chia hợp lệ.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $n$ — kích thước của bàn cờ.
• Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$ — hoán vị trên đường chéo chính.

Dữ liệu ra

Nếu không tồn tại cách chia hợp lệ, in ra $-1$.

Ngược lại, in ra $n$ dòng. Dòng thứ $i$ chứa $i$ số nguyên; số thứ $j$ trên dòng đó là giá trị $x$ nếu ô $(i,j)$ thuộc vùng có $x$ ô.

Nếu có nhiều cách chia hợp lệ, bạn có thể in ra cách bất kỳ.

Ràng buộc

• $1\le n\le 500$.
• $p_1,p_2,\dots ,p_n$ là một hoán vị của $\{1,2,\dots ,n\}$.

Ví dụ