Đặt quân hậu

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 \(2\) 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 \(2\) dòng, 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

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

Scoring

• Subtask \(1\): \(n \leq 10\).
• Subtask \(2\): \(n \leq 100\).
• Subtask \(3\): \(n \leq 500\).