An rất thích thú với trò chơi xếp hậu. Trò chơi như sau: Cho một bàn cờ vua \(n \times n\) ô và \(n\) quân hậu, tìm cách đặt tất cả \(n\) quân hậu lên bàn cờ mà không có \(2\) quân hậu nào chiếu nhau.

Sau nhiều giờ An đã xếp được \(n\) quân hậu lên bàn cờ \(n \times n\) mà không có hai quân hậu nào chiếu nhau. Sau đó An nhấc bỏ một số quân ra khỏi bàn cờ rồi đố Bình xếp các quân mà An vừa nhấc để xếp vào bàn cờ thỏa mãn không có hai quân hậu nào chiếu nhau.

Yêu cầu

Cho kích thước bàn cờ và trạng thái bàn cờ sau khi An đã nhấc bỏ một số quân, hãy tìm cách đặt các quân hậu còn lại lên bàn cờ mà không có hai hậu nào chiếu nhau.

Input

• Gồm nhiều bộ dữ liệu, mỗi bộ trên một dòng chứa số \(n\) và tiếp theo là \(n\) số mô tả trạng thái bàn cờ.
• Số thứ \(i\) là thứ tự cột của quân hậu đặt trên dòng \(i\), nếu số này bằng \(0\) nghĩa là quân hậu trên dòng đó đã bị nhấc ra.

Output

• Gồm nhiều dòng, mỗi dòng tương ứng với một bộ dữ liệu đầu vào.
• Mỗi dòng gồm \(n\) số, số thứ \(i\) là thứ tự cột của quân hậu đặt trên dòng \(i\), mô tả trạng thái sau khi đã đặt các quân còn lại lên bàn cờ mà không có hai quân hậu nào chiếu nhau.

Example

4 0 0 0 0
8 2 0 0 0 4 0 0 0

2 4 1 3
2 6 1 7 4 8 3 5

Constraints

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(3\) (\(60\%\) số điểm): \(n \le 500\).

Nguồn: Thầy Đông '21